Input
Output
Escaped in x minute(s).
Trapped!
Sample Input
3 4 5 S.... .###. .##.. ###.# ##### ##### ##.## ##... ##### ##### #.### ####E 1 3 3 S## #E# ### 0 0 0
Sample Output
Escaped in 11 minute(s). Trapped!
刚刚入门算法竞赛，做到此题，收获颇丰。
先放上本菜鸡第一次AC的代码：
1 #include<iostream> 2 #include<queue> 3 #include<string.h> 4 using namespace std; 5 6 7 int maze[31][31][31]={0}; 8 struct pos{ 9 int x,y,z; 10 pos(int x,int y,int z); 11 }; 12 queue<pos> q; 13 int time=0; 14 int x,y,z,_x,_y,_z; 15 pos::pos(int x,int y,int z){ 16 this->x=x; 17 this->y=y; 18 this->z=z; 19 } 20 void BFS(pos p0); 21 22 int main(){ 23 24 cin >>z>>x>>y; 25 while(z!=0||x!=0||y!=0){ 26 int begin_x,begin_y,begin_z; 27 //建立3维棋盘 28 for(int i=0;i<z;i++){ 29 for(int j=0;j<x;j++){ 30 for(int k=0;k<y;k++){ 31 char in; 32 cin >>in; 33 if(in==‘S‘){ 34 maze[j][k][i]=0; 35 begin_x=j;begin_y=k;begin_z=i; 36 }else if(in==‘E‘){ 37 maze[j][k][i]=0; 38 _x=j;_y=k;_z=i; 39 }else if(in==‘#‘){ 40 maze[j][k][i]=-10; 41 }else if(in==‘.‘){ 42 maze[j][k][i]=0; 43 } 44 } 45 } 46 } 47 pos p0(begin_x,begin_y,begin_z); 48 BFS(p0); 49 memset(maze,0,sizeof(maze)); 50 time=0; 51 while(!q.empty()){ 52 q.pop(); 53 } 54 cin >>z>>x>>y; 55 } 56 system("pause"); 57 return 0; 58 59 } 60 61 void BFS(pos p0){ 62 maze[p0.x][p0.y][p0.z]=0; 63 q.push(p0); 64 bool OK=false; 65 while(!q.empty()){ 66 pos u=q.front(); 67 q.pop(); 68 pos left(u.x,u.y-1,u.z),right(u.x,u.y+1,u.z); 69 pos forward(u.x-1,u.y,u.z),back(u.x+1,u.y,u.z); 70 pos up(u.x,u.y,u.z+1),down(u.x,u.y,u.z-1); 71 if(left.y>=0&&maze[left.x][left.y][left.z]==0){ 72 maze[left.x][left.y][left.z]=maze[u.x][u.y][u.z]+1; 73 if(left.x==_x&&left.y==_y&&_z==left.z){ 74 OK=true; 75 time=maze[left.x][left.y][left.z]; 76 break; 77 } 78 q.push(left); 79 } 80 if(right.y<=y-1&&maze[right.x][right.y][right.z]==0){ 81 82 maze[right.x][right.y][right.z]=maze[u.x][u.y][u.z]+1; 83 if(right.x==_x&&right.y==_y&&_z==right.z){ 84 OK=true; 85 time=maze[right.x][right.y][right.z]; 86 break; 87 } 88 q.push(right); 89 } 90 if(forward.x>=0&&maze[forward.x][forward.y][forward.z]==0){ 91 92 maze[forward.x][forward.y][forward.z]=maze[u.x][u.y][u.z]+1; 93 if(forward.x==_x&&forward.y==_y&&_z==forward.z){ 94 OK=true; 95 time=maze[forward.x][forward.y][forward.z]; 96 break; 97 } 98 q.push(forward); 99 } 100 if(back.x<=x-1&&maze[back.x][back.y][back.z]==0){ 101 102 maze[back.x][back.y][back.z]=maze[u.x][u.y][u.z]+1; 103 if(back.x==_x&&back.y==_y&&_z==back.z){ 104 OK=true; 105 time=maze[back.x][back.y][back.z]; 106 break; 107 } 108 q.push(back); 109 } 110 if(up.z<=z-1&&maze[up.x][up.y][up.z]==0){ 111 112 maze[up.x][up.y][up.z]=maze[u.x][u.y][u.z]+1; 113 if(up.x==_x&&up.y==_y&&_z==up.z){ 114 OK=true; 115 time=maze[up.x][up.y][up.z]; 116 break; 117 } 118 q.push(up); 119 } 120 if(down.z>=0&&maze[down.x][down.y][down.z]==0){ 121 122 maze[down.x][down.y][down.z]=maze[u.x][u.y][u.z]+1; 123 if(down.x==_x&&down.y==_y&&_z==down.z){ 124 OK=true; 125 time=maze[down.x][down.y][down.z]; 126 break; 127 } 128 q.push(down); 129 } 130 } 131 if(OK){ 132 cout <<"Escaped in "<<time<<" minute(s)."<<endl; 133 }else{ 134 cout <<"Trapped!"<<endl; 135 } 136 }
这个代码虽然能AC，但是存在很多问题：
针对第一个问题，可以用三个数组分别记录六个方向的三个坐标的变动，这样可以将6个if语句合为1个
int dx[] = {0,1,0,-1,0,0},dy[] = {1,0,-1,0,0,0},dz[] = {0,0,0,0,1,-1};//拓展操作可以直接定义数组来进行拓展
int x = t.first + dx[i],y = t.second + dy[i],z = t.third + dz[i];
针对第二个问题，应该用每个格子的权值表示从起点到这个格子所需的分钟，这样便巧妙的记录了到达每个格子的所需时间
//时间在格子间的传递 maze[left.x][left.y][left.z]=maze[u.x][u.y][u.z]+1;
本题为典型的BFS模板题，将常见的二维图改成了三维，但是方法没有变。
原文：https://www.cnblogs.com/shiyu-coder/p/13128558.html