题目大意：给出一个迷宫，一个男孩和一个女孩还有两只鬼，男孩每秒钟走3格，女孩每秒钟走1格，鬼每秒钟向四周分裂2格，问男孩和女孩能否在鬼占领迷宫之前汇合，能的话输出汇合时间，否则输出-1
思路： 双向BFS，分别从男孩和女孩进行BFS，然后判断是否被鬼所占领，那个地方有没有走过。男孩和女孩走的地方可以用不同的标记来进行，如果同时可以走到同一个地方，说明是可以的。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 805;
int t,n,m,vis[N][N],zx1,zx2,zy1,zy2,mx,my,gx,gy,step;
char G[N][N];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
struct node
{int x,y;node(int xx,int yy){x=xx; y=yy;}
};
bool ok(int x,int y)
{if (x < 0 || y < 0 || x >= n || y >= m || G[x][y] == 'X') return false;if(abs(x-zx1)+abs(y-zy1)<=2*step) return false;if(abs(x-zx2)+abs(y-zy2)<=2*step) return false;return true;
}
int bfs()
{memset(vis,0,sizeof(vis));vis[mx][my]=1;vis[gx][gy]=2;step=0;queue<node>qm,qg; // man 和 girlqm.push(node(mx,my));qg.push(node(gx,gy));while(!qm.empty()&&!qg.empty()){step++;for(int k=1;k<=3;k++){for(int i=0;i<qm.size();i++){node t = qm.front();qm.pop();if(!ok(t.x,t.y)) continue;for(int j=0;j<4;j++){int fx=t.x+dx[j];int fy=t.y+dy[j];if(!ok(fx,fy) || vis[fx][fy]==vis[t.x][t.y])continue;if(vis[fx][fy] + vis[t.x][t.y]==3)return step;vis[fx][fy]=vis[t.x][t.y];qm.push(node(fx,fy));}}}for(int i=0;i<qg.size();i++){node t = qg.front();qg.pop();if(!ok(t.x,t.y)) continue;for(int j=0;j<4;j++){int fx=t.x+dx[j];int fy=t.y+dy[j];if(!ok(fx,fy) || vis[fx][fy]==vis[t.x][t.y])continue;if(vis[fx][fy]+vis[t.x][t.y]==3)return step;vis[fx][fy]=vis[t.x][t.y];qg.push(node(fx,fy));}}}return -1;
}
int main()
{cin>>t;while(t--){cin>>n>>m;for(int i=0;i<n;i++){cin>>G[i];}int cnt=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(G[i][j]=='Z')if(!cnt)zx1=i,zy1=j,cnt++;elsezx2=i,zy2=j;if(G[i][j]=='M') mx=i,my=j;if(G[i][j]=='G') gx=i,gy=j;}}cout<<bfs()<<endl;}
}