n*m地图上有
‘. ’：路
‘X’：墙
’Z’：鬼，每秒蔓延2个单位长度，，可以穿墙，共两个，每秒开始时鬼先动
‘M’：一号，每分钟可移动3个单位长度
‘G’：二号，每分钟课移动1个单位长度
问两人是否可以成功碰面，再不被鬼吃掉的前提下
双向广搜，对于‘M’，每次搜三步，对于‘G’，每次搜一步。和鬼的距离可用曼哈顿距离计算判断
注意每秒开始时鬼先移动
#include "stdio.h"#include "string.h"#include "algorithm"#include "queue"using namespace std;const int dir[4][2]={ {1,0},{-1,0},{0,1},{0,-1} };char str[810][810];int used[2][810][810];int g_x,g_y,m_x,m_y,n,m,step;struct node{int x,y;}ncur,z[2];queue<node>q[2];void init(){int i,j,cnt;scanf("%d%d",&n,&m);for (i=0;i<n;i++)scanf("%s",str[i]);cnt=0;for (i=0;i<n;i++)for (j=0;j<m;j++){if (str[i][j]=='G'){g_x=i; g_y=j;}if (str[i][j]=='M'){m_x=i; m_y=j;}if (str[i][j]=='Z'){z[cnt].x=i;z[cnt++].y=j;}}}int judge(node b){if (b.x<0 || b.y<0 || b.x>=n || b.y>=m) return 0;if (str[b.x][b.y]=='X') return 0;if ((abs(b.x-z[0].x)+abs(b.y-z[0].y))<=2*step) return 0;if ((abs(b.x-z[1].x)+abs(b.y-z[1].y))<=2*step) return 0;return 1;}int bfs(int w){node cur,next;int i,sum;sum=q[w].size();while (sum–){cur=q[w].front();q[w].pop();if (judge(cur)==0) continue;for (i=0;i<4;i++){next.x=cur.x+dir[i][0];next.y=cur.y+dir[i][1];if (judge(next)==0) continue;if (used[w][next.x][next.y]==0){if (used[w^1][next.x][next.y]==1) return 1;used[w][next.x][next.y]=1;q[w].push(next);}}}return 0;}int solve(){while (!q[0].empty()) q[0].pop();while (!q[1].empty()) q[1].pop();ncur.x=m_x;ncur.y=m_y;q[0].push(ncur);ncur.x=g_x;ncur.y=g_y;q[1].push(ncur);memset(used,0,sizeof(used));used[0][m_x][m_y]=used[1][g_x][g_y]=1;step=0;while ((!q[0].empty()) || (!q[1].empty())){step++;if (bfs(0)==1) return step;if (bfs(0)==1) return step;if (bfs(0)==1) return step;if (bfs(1)==1) return step;}return -1;}int main(){int Case;scanf("%d",&Case);while (Case–){init();printf("%d\n",solve());}return 0;}
都成为命途中美丽的点缀，看天，看雪，安安静静，不言不语都是好风景。
