题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3085
题目大意：给你一张n*m地图上，上面有有
‘. ’：路
‘X'：墙
’Z'：鬼，每秒移动2步，可以穿墙，开始有两个，每开始时鬼先动。
‘M’：男生，每秒可走3步。
‘G’：女生，每秒可走1步。
解题思路：第一次写双向BFS，写了我好久，开始还是想着先bfs计算step[x][y][t]把每个位置被鬼占据的时间处理一下然后再用双向BFS计算两人相遇时间。后来发现因为鬼可以穿墙，可以直接用曼哈顿距离判断是否会被鬼抓到。还有，开始我都不知道每秒走三步怎么搞。。。后来看了网上的博客，知道可以通用size限制一下出队数，三次bfs实现每秒走三步。太乱了，稍微总结一下：
①两人给vis[x][y]分别标记1,2当某次bfs遇到不同标记说明两人相遇。
②用曼哈顿距离判断时间t走到某个位置是否会被鬼抓到。
③因为鬼先行动，每次t+1时，在人行动前要判断在当前位置会不会被鬼抓到。
④用size=q[mark].size()控制每次出队数，实现一秒走三步。
⑤最坑爹的一点，用scanf("%c",&map[i][j])无限超时，感觉里面绝对有不正常的数据，后来用scanf("%s",map[i]+1)每次输入一行才过掉。
代码：
#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=; int n,m,t;
int d[][]={{-,},{,},{,-},{,}};
char map[N][N];
int vis[N][N]; struct node{
int x,y;
}M,G,pre,now,a[];
queue<node>q[]; bool judge(int x,int y){
if(x<||y<||x>n||y>m||map[x][y]=='X')
return false;
//利用曼哈顿距离判断是否会被鬼抓到
for(int i=;i<=;i++){
if(abs(x-a[i].x)+abs(y-a[i].y)<=*t)
return false;
}
return true;
} bool bfs(int mark){
//小技巧，利用size就可以控制出队的都是上一步的，而不会将这一步的也出队，就能实现走3步了。
int size=q[mark].size();
while(size--){
pre=q[mark].front();
q[mark].pop();
//鬼在人之前行动，时间每增加1，先判断鬼能不能把人吃掉
if(!judge(pre.x,pre.y))
continue;
for(int i=;i<;i++){
int xx=pre.x+d[i][];
int yy=pre.y+d[i][];
if(!judge(xx,yy))
continue;
//遇到不同标记说明两人相遇
if(vis[xx][yy]){
if(vis[xx][yy]!=mark)
return true;
else
continue;
}
vis[xx][yy]=mark;
now.x=xx;
now.y=yy;
q[mark].push(now);
}
}
return false;
} int solve(){
//清空队列
while(!q[].empty()) q[].pop();
while(!q[].empty()) q[].pop();
q[].push(M);
q[].push(G);
vis[M.x][M.y]=,vis[G.x][G.y]=;
t=;
//双向bfs
while(!q[].empty()||!q[].empty()){
t++;
for(int i=;i<=;i++){
if(bfs())
return t;
}
if(bfs())
return t;
}
return -;
} int main(){
int T;
scanf("%d",&T);
while(T--){
memset(vis,,sizeof(vis));
scanf("%d%d",&n,&m);
//注意用scanf("%c",map[i][j])会超时
for(int i=,cnt=;i<=n;i++){
scanf("%s",map[i]+);
for(int j=;j<=m;j++){
if(map[i][j]=='M')
M.x=i,M.y=j;
if(map[i][j]=='G')
G.x=i,G.y=j;
if(map[i][j]=='Z')
a[++cnt].x=i,a[cnt].y=j;
}
}
printf("%d\n",solve());
}
return ;
}