企业官网建设流程全解析

题目：1248：Dungeon Master

题目描述

这题是一个三维的迷宫题目，其中用‘.’表示空地，‘#’表示障碍物，‘S’表示起点，‘E’表示终点，求从起点到终点的最小移动次数，解法和二维的类似，只是在行动时除了东南西北移动外还多了上下。可以上下左右前后移动，每次都只能移到相邻的空位，每次需要花费一分钟，求从起点到终点最少要多久。

输入

多组测试数据。

一组测试测试数据表示一个三维迷宫：

前三个数，分别表示层数、一个面的长和宽，后面是每层的平面图。前三个数据为三个零表示结束。

输出

最小移动次数。

时空限制

1s / 64MB

样例输入

3 4 5 S.... .###. .##.. ###.# ##### ##### ##.## ##... ##### ##### #.### ####E 1 3 3 S## #E# ### 0 0 0

样例输出

Escaped in 11 minute(s). Trapped!

提示

对于题目给出数据的含义就是输入l，r，c，分别代表迷宫有l层，每层长宽分别是c，r。对于数据以可以这样移动:

(1,1,1)->(1,1,2)->(1,1,3)->(1,1,4)->(1,1,5)->(1,2,5)->

(1,3,5)->(1,3,4)->(1,4,4)->(2,4,4)->(2,4,5)->(3,4,5)

共11步就可以到达终点 对于数据二明显不能到达，则输出Trapped！

这题用BFS解，每次去队首元素，如果是终点则输出结果移动的次数，否则，从该点开始分别向东南西北上下移动（如果可以走的话）并继续搜，如果到队列为空还没搜到解法，则说明无解。

代码

#include<bits/stdc++.h>usingnamespacestd;constintN=100+10;inth,n,m,sx,sy,sz,ex,ey,ez;charg[N][N][N];intdis[N][N][N];intdx[10]={-1,1,0,0,0,0},dy[10]={0,0,-1,1,0,0},dz[10]={0,0,0,0,1,-1};structnode{intx,y,z;};voidbfs(intx1,inty1,intz1){queue<node>q;q.push({x1,y1,z1});dis[x1][y1][z1]=0;while(!q.empty()){node t=q.front();q.pop();for(inti=0;i<6;i++){intxx=t.x+dx[i],yy=t.y+dy[i],zz=t.z+dz[i];if(xx<1||xx>n||yy<1||yy>m||zz<1||zz>h)continue;if(g[xx][yy][zz]=='#')continue;if(dis[xx][yy][zz]==-1){q.push({xx,yy,zz});dis[xx][yy][zz]=dis[t.x][t.y][t.z]+1;if(xx==ex&&yy==ey&&zz==ez)return;}}}}intmain(){while(cin>>h>>n>>m,h||n||m){for(intk=1;k<=h;k++)for(inti=1;i<=n;i++)for(intj=1;j<=m;j++){cin>>g[i][j][k];if(g[i][j][k]=='S')sx=i,sy=j,sz=k;if(g[i][j][k]=='E')ex=i,ey=j,ez=k;dis[i][j][k]=-1;}bfs(sx,sy,sz);if(dis[ex][ey][ez]>-1)cout<<"Escaped in "<<dis[ex][ey][ez]<<" minute(s)."<<endl;elseputs("Trapped!");}return0;}

结果