题解 P9116/SP6956 【Mecho】

zhzkiller · 2023-07-12 18:00:52 · 题解

题外话

我本人写题解本来不写这个。

它不是紫题，为什么也要卡我 3 个小时！！！

题目描述

这道题要求我们求出一个最大的等待时间，使得小熊 Mecho 能够及时回到家里而不被蜜蜂堵住去路。

解题思路（正解）

很容易看出来这是一道广搜题，再一看就能看出来这是经典的双向 bfs 算法，而且本题答案具有单调性（更小的答案一定满足，更大的答案一定不满足）。我们只需每次二分答案后进行合法检查，具体表现为让小熊先搜 S 步后让蜜蜂也搜 1 步，看小熊是否能在 bfs 结束前到达终点即可。

请注意此题解不是上述算法。

如果想练习双向 bfs 请移步它处。

解题思路（本人解法）

还是广搜和二分答案不变，我的做法是将蜜蜂所经过的路径打上类似时间戳的标记，在每次合法检查时仅对小熊进行移动，并实时与标记数组进行比较。该做法优点是比双向 bfs 好想，也好实现，缺点是有过多很细的细节需要注意，修死我了。

这个题解主要作用在于补充做题思路和服务想 AC 本题但是没有系统学习过双向 bfs 的同学。如果你没有更好的算法，那就和我一起坐牢吧~

完结撒花~

献上蒟蒻的 AC 代码：

#include <bits/stdc++.h>
using namespace std;
const int N=810;

int n,k;
int stx,sty,edx,edy;
char a[N][N];
int dfn[N][N],d[N][N],cnt[N][N];
bool vis[N][N],v[N][N];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
queue< pair<int,int> > Q;

bool check(int t)
{
    memset(v,0,sizeof(v));
    Q.push({stx,sty});
    v[stx][sty]=true;d[stx][sty]=t==-1?0:t;
    while(Q.size())
    {
        int sx=Q.front().first,sy=Q.front().second;Q.pop();
        if(t==-1&&d[sx][sy]>dfn[sx][sy]) continue;
        if(sx==edx&&sy==edy)
        {
            while(Q.size()) Q.pop();
            return true;
        }
        int now=(d[sx][sy]-(t==-1?0:t))%k?(d[sx][sy]-(t==-1?0:t))/k+1:(d[sx][sy]-(t==-1?0:t))/k;
        for(int i=0;i<4;i++)
        {
            int tx=sx+dx[i],ty=sy+dy[i];
            if(tx&&ty&&tx<=n&&ty<=n&&!v[tx][ty]&&(a[tx][ty]=='G'||a[tx][ty]=='D')&&
            ((t==-1?0:t)+now<dfn[tx][ty]-(k==1?k:0)||(t==-1?0:t)+now==dfn[tx][ty]
            -(k==1?k:0)&&cnt[sx][sy]!=(k-1?k-1:k))&&(now!=0||t+1<=dfn[tx][ty]))
            {
                if(cnt[sx][sy]==k&&t+now+1>dfn[tx][ty]) continue;
                v[tx][ty]=true;
                Q.push({tx,ty});
                if(t==-1)
                {
                    cnt[tx][ty]=cnt[sx][sy]+1;
                    if(cnt[tx][ty]==k+1)
                    {
                        d[tx][ty]=d[sx][sy]+1;
                        cnt[tx][ty]=1;
                    }
                    else d[tx][ty]=d[sx][sy];
                }
                else d[tx][ty]=d[sx][sy]+1;
            }
        }
    }
    return false;
}

void bfs()
{
    dfn[edx][edy]=1e9;cnt[stx][sty]=k;
    while(Q.size())
    {
        int sx=Q.front().first,sy=Q.front().second;Q.pop();
        for(int i=0;i<4;i++)
        {
            int tx=sx+dx[i],ty=sy+dy[i];
            if(tx&&ty&&tx<=n&&ty<=n&&!vis[tx][ty]&&(a[tx][ty]=='G'||a[tx][ty]=='M'))
            {
                if(!dfn[tx][ty]) dfn[tx][ty]=dfn[sx][sy]+1;
                Q.push({tx,ty});vis[tx][ty]=true;
            }
        }
    }
}

int main()
{
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
            if(a[i][j]=='H') Q.push({i,j}),vis[i][j]=true;
            else if(a[i][j]=='M') stx=i,sty=j;
            else if(a[i][j]=='D') edx=i,edy=j;
        }
    }

    bfs();

    if(!check(-1))
    {
        printf("-1");
        return 0;
    }

    int l=0,r=n*n;
    while(l<r)
    {
        int mid=(l+r+1)>>1;
        if(mid<dfn[stx][sty]&&check(mid)) l=mid;
        else r=mid-1;
    }
    printf("%d",l);
    return 0;
}

必要细节

1.多测必清空，队列要出完。

2.蜜蜂并不能占领小熊的家，即：

a[tx][ty]!='D';

3.二分注意上下界及如何取 mid 的问题。

此代码细节

1.mid<dfn[stx][sty] 时可以不进搜索直接二分，优化不少。

2.时刻记得保持 d[sx][sy]<=dfn[sx][sy]。