View Code
1 #include<cstdio> 2 #include<cstring> 3 #include<cstdlib> 4 #include<queue> 5 #include<algorithm> 6 #define N 36 7 using namespace std; 8 char map[N][N][N]; 9 int vis[N][N][N]; 10 int dx[6]={0,-1,0,1,0,0}; 11 int dy[6]={-1,0,1,0,0,0}; 12 int dz[6]={0,0,0,0,1,-1}; 13 14 int l,r,c,sx,sy,sz,ans; 15 struct point { 16 int x,y,z; 17 int lev; 18 }; 19 point p,pp; 20 queue<point>q; 21 22 void bfs(){ 23 int i,j; 24 p.z=sz; 25 p.x=sx; 26 p.y=sy; 27 p.lev=0; 28 ans=999999; 29 vis[sz][sx][sy]=1; 30 q.push(p); 31 while(!q.empty()){ 32 p=q.front(); 33 q.pop(); 34 pp.x=p.x; 35 pp.y=p.y; 36 pp.x=p.z; 37 38 if(map[p.z][p.x][p.y]=='E'){ 39 if(ans>p.lev) 40 ans=p.lev; 41 while(!q.empty()) 42 q.pop(); 43 } 44 for(i=0;i<6;i++){ 45 pp.x=p.x+dx[i]; 46 pp.y=p.y+dy[i]; 47 pp.z=p.z+dz[i]; 48 if(pp.x<0||pp.x>=r||pp.y<0||pp.y>=c||pp.z<0||pp.z>=l||vis[pp.z][pp.x][pp.y]==1||map[pp.z][pp.x][pp.y]=='#') 49 continue; 50 if(map[pp.z][pp.x][pp.y]=='E'){ 51 vis[pp.z][pp.x][pp.y]=1; 52 pp.lev=p.lev+1; 53 q.push(pp); 54 } 55 if(map[pp.z][pp.x][pp.y]=='.'){ 56 vis[pp.z][pp.x][pp.y]=1; 57 pp.lev=p.lev+1; 58 q.push(pp); 59 } 60 } 61 } 62 if(ans==999999) 63 printf("Trapped!\n"); 64 else 65 printf("Escaped in %d minute(s).\n",ans); 66 return ; 67 } 68 69 int main(){ 70 int i,j,k; 71 while(scanf("%d%d%d",&l,&r,&c)==3,l+r+c){ 72 memset(map,'#',sizeof(map)); 73 memset(vis,0,sizeof(vis)); 74 for(k=0;k<l;k++){//层数 75 for(i=0;i<r;i++){//行数 76 scanf("%s",map[k][i]); 77 } 78 getchar(); 79 } 80 81 for(k=0;k<l;k++) 82 for(i=0;i<r;i++) 83 for(j=0;j<c;j++){ 84 if(map[k][i][j]=='S'){ 85 sz=k; 86 sx=i; 87 sy=j; 88 break; 89 } 90 } 91 92 bfs(); 93 } 94 return 0; 95 }
题目大意：
给出一三维空间的地牢,要求求出由字符'S'到字符'E'的最短路径
移动方向可以是上，下，左，右，前，后，六个方向
每移动一次就耗费一分钟，要求输出最快的走出时间。
不同L层的地图，相同RC坐标处是连通的