Dungeon Master ( bfs )
题目大意
一个三维迷宫,已知起点S,终点E,只能前后左右上下前进,求最短路径。若有,输出所花时间;反之,输出trapped.
思路
思路简单,直接套bfs板子。
第一个错误点在于没有将E标位. 导致结果错误;
第二个错误点在于针对于多组数据,没有将队列里的垃圾数据清空,导致结果错误。
AC代码
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> using namespace std; const int maxn=35; int l,r,c,ans; char mp[maxn][maxn][maxn]; int vis[maxn][maxn][maxn]; typedef struct{ int x,y,z; int step; }N; N S,E; queue <N> q; int d[6][3]={{-1,0,0},{1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}}; void bfs(){ q.push(S); vis[S.x][S.y][S.z]=1; while(q.size()){ N fa=q.front(); if(fa.x==E.x&&fa.y==E.y&&fa.z==E.z){ ans=1; printf("Escaped in %d minute(s).\n",fa.step); while(q.size()){ q.pop(); } return ; } q.pop(); N son; for(int i=0;i<6;i++){ son.x=fa.x+d[i][0],son.y=fa.y+d[i][1],son.z=fa.z+d[i][2]; if(son.x>=0&&son.y>=0&&son.z>=0&&son.x<l&&son.y<r&&son.z<c&&!vis[son.x][son.y][son.z]&&mp[son.x][son.y][son.z]=='.'){ vis[son.x][son.y][son.z]=1; son.step=fa.step+1; q.push(son); } } } ans=0; return ; } int main(){ while(1){ scanf("%d%d%d",&l,&r,&c); if(l==0&&r==0&&c==0) break; memset(vis,0,sizeof(vis)); memset(mp,0,sizeof(mp)); for(int i=0;i<l;i++){ for(int j=0;j<r;j++){ for(int k=0;k<c;k++){ cin>>mp[i][j][k]; if(mp[i][j][k]=='S'){ S.x=i,S.y=j,S.z=k,S.step=0; }else if(mp[i][j][k]=='E'){ mp[i][j][k]='.'; E.x=i,E.y=j,E.z=k; } } } } ans=0; bfs(); if(!ans) printf("Trapped!\n"); } return 0; }