發現直接搜索比較麻煩，但是要同時兩個人一起走容易想到雙向bfs，比較普通，

在判斷是否碰到ghost時只要比較兩點的曼哈頓距離大小和step*2（即ghost擴散的距離）即可，仔細思考也是可以想到的

#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<algorithm> using namespace std; const int maxn=809; struct node{int x,y;node(){}node(int a,int b){x=a,y=b;} }mon[2]; queue<node>pq[2]; int n,m; char maze[maxn][maxn]; int used[2][maxn][maxn]; int dx[]={1,-1,0,0}; int dy[]={0,0,1,-1}; int step; int check(node a){if(a.x<0 || a.y<0 || a.x>=n || a.y>=m)return 0;if(maze[a.x][a.y]=='X')return 0;if((abs(a.x-mon[0].x)+abs(a.y-mon[0].y))<=2*step)return 0;if((abs(a.x-mon[1].x)+abs(a.y-mon[1].y))<=2*step)return 0;return 1; } int bfs(int w){ // while(!pq[w].empty()){int sum = pq[w].size();//這里不能搜完 while (sum--){int x=pq[w].front().x,y=pq[w].front().y;pq[w].pop();if(!check(node(x,y)))continue;for(int i=0;i<4;i++){int xx=x+dx[i],yy=y+dy[i];if(!check(node(xx,yy)))continue;if(!used[w][xx][yy]){if(used[w^1][xx][yy]==1)return 1;used[w][xx][yy]=1;pq[w].push(node(xx,yy));}}}return 0; } int ax,ay,bx,by; int solve(){while(!pq[0].empty())pq[0].pop();while(!pq[1].empty())pq[1].pop();pq[0].push(node(ax,ay));pq[1].push(node(bx,by));memset(used,0,sizeof(used));used[0][ax][ay]=used[1][bx][by]=1;step=0;while(!pq[0].empty() || !pq[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 T;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);int cnt=0;for(int i=0;i<n;i++)scanf("%s",maze[i]);for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(maze[i][j]=='G')bx=i,by=j;else if(maze[i][j]=='M')ax=i,ay=j;else if(maze[i][j]=='Z')mon[cnt].x=i,mon[cnt++].y=j;}}printf("%d\n",solve());}}

?

轉載于:https://www.cnblogs.com/superminivan/p/10858739.html

總結

以上是生活随笔為你收集整理的[题解]（双向bfs）hdu_3085_Nightmare Ⅱ的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。