做在二维地图上移动的模拟题时，绝大多数情况都需要使用 \(bfs\)，其中 \(99\%\) 的情况都是只走一步（也就是上下左右四个方向选一个，并移动一格）。那么如果每一次可以连续走 \(k\) 步，我们应当如何处理呢？
M - Nightmare Ⅱ
重点看 bfs 函数部分，将 \(while\) 函数的退出条件改成了计数器减为 0。这样就可以做到在 bfs 的每一步转移时，用到的都是上一次走了相同步数的点。
本题也是练习双向 bfs 的好题。通过按照时间戳 cnt 同时模拟两个人的 bfs 过程，判断两个人是否可以相遇 当且仅当 两个人可以在某 cnt 时走到同一个点上。而与鬼魂的相遇直接简单地利用曼哈顿距离处理。
#include<algorithm>
#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
struct str
{int x,y;
}z[2],b,g;
int t,n,m,cnt;
int drt[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
char mapp[801][801];
bool vis[2][801][801];
queue<str> que[2];
bool check(str t)
{bool flag=true;if(abs(t.x-z[0].x)+abs(t.y-z[0].y)<=2*cnt)//判断鬼是否已经到达某一点flag=false;else if(abs(t.x-z[1].x)+abs(t.y-z[1].y)<=2*cnt)flag=false;if(t.x<0||t.y<0||t.x>=n||t.y>=m)//判断即将要走的点是否在界外 flag=false;else if(mapp[t.x][t.y]=='X')flag=false;return flag;
}
bool bfs(int x)
{int tot=que[x].size();//每次连续弹出、处理的点都是同一步的点str now,nxt;while(tot--) // !!! 精妙之处，固定弹出队列元素的数量。设当前是在模拟走连续k步中的第j步，则弹出的点一定是恰好走了j-1步的所有点。等到处理完这些点后，队列内存留的是所有恰好走了j步的点，形成递推关系。{now=que[x].front();que[x].pop();if(!check(now))//判断鬼是否已经到达now所在的点continue;for(int i=0;i<4;i++){nxt.x=now.x+drt[i][0];nxt.y=now.y+drt[i][1];if(check(nxt)&&!vis[x][nxt.x][nxt.y])//判断nxt所在的点是否出界、是否已经过{vis[x][nxt.x][nxt.y]=true;if(vis[x][nxt.x][nxt.y]&&vis[1-x][nxt.x][nxt.y])//判断nxt所在的点是否被G和M都走过return true;que[x].push(nxt);}}}return false;
}
int fun()
{while(!que[0].empty())//每次处理一组新的数据前先将队列清空que[0].pop();while(!que[1].empty())que[1].pop();memset(vis,0,sizeof(vis));que[0].push(b);que[1].push(g);vis[0][b.x][b.y]=vis[1][g.x][g.y]=true;while(!que[0].empty()||!que[1].empty()){cnt++;//统计时间for(int i=0;i<3;i++)//M每个单位时间走三步if(bfs(0))return cnt;if(bfs(1))//G每个单位时间走一步return cnt;}return -1;
}
int main()
{scanf("%d",&t);while(t--){int zx=0;cnt=0;scanf("%d%d",&n,&m);for(int i=0;i<n;i++){scanf("%s",&mapp[i]);for(int j=0;j<m;j++){if(mapp[i][j]=='Z'){z[zx].x=i,z[zx].y=j;zx++;}if(mapp[i][j]=='M')b.x=i,b.y=j;if(mapp[i][j]=='G')g.x=i,g.y=j;}}printf("%d\n",fun());}return 0;
}