题意:给你一个L.R.C的地牢(L*R*C的三维地牢)。求出从s到e的最短路。
Sample Input
3 4 5 S.... .###. .##.. ###.# ##### ##### ##.## ##... ##### ##### #.### ####E 1 3 3 S## #E# ### 0 0 0
Sample Output
Escaped in 11 minute(s). Trapped!
#include <iostream> #include <cstdio> #include <algorithm> #include <string> #include <cmath> #include <cstring> #include <queue> #include <set> #include <vector> #include <stack> #include <map> #include <iomanip> #define PI acos(-1.0) #define Max 2005 #define inf 1<<28 using namespace std; int L,R,C; char Map[40][40][40]; bool visit[40][40][40]; struct kdq { int xx,yy,zz; int step; }q[1000000]; int movex[6]={0,0,1,-1,0,0};//东,西,南,北,上,下 int movey[6]={1,-1,0,0,0,0}; int movez[6]={0,0,0,0,1,-1}; int inmap(int x,int y,int z) { if(z>=0&&z<L&&x>=0&&x<R&&y>=0&&y<C) return 1; return 0; } int bfs(int x,int y,int z) { kdq a; a.xx=x,a.yy=y,a.zz=z,a.step=0; int num=0,cnt=0; q[num]=a; num++; visit[z][x][y]=1; while(num>cnt) { kdq temp=q[cnt]; cnt++; if(Map[temp.zz][temp.xx][temp.yy]=='E') { return temp.step; } for(int i=0;i<6;i++) { int tx=temp.xx+movex[i]; int ty=temp.yy+movey[i]; int tz=temp.zz+movez[i]; if(Map[tz][tx][ty]!='#'&&!visit[tz][tx][ty]&&inmap(tx,ty,tz)) { kdq now; now.xx=tx,now.yy=ty,now.zz=tz; now.step=temp.step+1; visit[tz][tx][ty]=1; q[num]=now; num++; } } } } int main() { int i,j,k; while(scanf("%d%d%d",&L,&R,&C)&&(L+R+C)) { int sx,sy,sz,ex,ey,ez; memset(visit,0,sizeof(visit)); for(i=0; i<L; i++) for(j=0; j<R; j++) for(k=0; k<C; k++) { cin>>Map[i][j][k]; if(Map[i][j][k]=='S') { sz=i; sx=j; sy=k; } if(Map[i][j][k]=='E') { ez=i; ex=j; ey=k; } } int ans=bfs(sx,sy,sz); if(visit[ez][ex][ey]) printf("Escaped in %d minute(s).\n",ans); else puts("Trapped!"); } return 0; }
很模板的一道BFS,只需加一维的坐标就可以了