题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3085
地图中有两个鬼,两个人M和G,步长不同,鬼有曼哈顿距离计算的领域,问人能否相遇,实际上可以通过双向BFS求解。
注意每次点从队列中取出来的时候进行判断是否合法,实时判断,因为鬼是先进行分裂的,并且扩展之后的点也要先判断是否在鬼的领域中。
代码:
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; #define maxn 810 int n,m; char s[maxn][maxn]; int gx,gy,mx,my,px,py,qx,qy; int dx[]={0,0,-1,1},dy[]={-1,1,0,0}; bool vis1[maxn][maxn],vis2[maxn][maxn]; int valid(int x,int y,int k){ if(x<=0 || x>n || y<=0 || y>m)return false; if(abs(x-px)+abs(y-py) <= 2*k)return false; if(abs(x-qx)+abs(y-qy) <= 2*k)return false; if(s[x][y]=='X')return false; return true; } int bfs(){ queue< pair<int,int> > q1,q2; q1.push(make_pair(mx,my)); q2.push(make_pair(gx,gy)); memset(vis1,0,sizeof(vis1)); memset(vis2,0,sizeof(vis2)); vis1[mx][my]=1; vis2[gx][gy]=1; if(mx==gx && my==gy)return 0; int ans=0; int size; while(!q1.empty() || !q2.empty()){ ans++; int loop=3; while(loop--){ size=q1.size(); while(size--){ int x=q1.front().first; int y=q1.front().second; q1.pop(); if(!valid(x,y,ans))continue;//鬼先分裂 for(int i=0;i<4;i++){ int xx=x+dx[i]; int yy=y+dy[i]; if(valid(xx,yy,ans) && !vis1[xx][yy]){ vis1[xx][yy]=1; q1.push(make_pair(xx,yy)); } } } } int size=q2.size(); while(size--){ int x=q2.front().first; int y=q2.front().second; q2.pop(); if(!valid(x,y,ans))continue; for(int i=0;i<4;i++){ int xx=x+dx[i]; int yy=y+dy[i]; if(valid(xx,yy,ans) && !vis2[xx][yy]){ if(vis1[xx][yy])return ans; vis2[xx][yy]=1; q2.push(make_pair(xx,yy)); } } } } return -1; } int main(){ int t; cin>>t; while(t--){ bool first = true; cin>>n>>m; for(int i=1;i<=n;i++)scanf("%s",s[i]+1); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ if(s[i][j]=='G'){ gx=i; gy=j; } else if(s[i][j]=='M'){ mx=i; my=j; } else if(s[i][j]=='Z'){ if(first){ px=i; py=j; first=false; }else{ qx=i; qy=j; } } } cout<<bfs()<<endl; } return 0; }