B-Dungeon Master（地牢主）

Dungeon Master

You are trapped in a 3D dungeon and need to find the quickest way out! The dungeon is composed of unit cubes which may or may not be filled with rock. It takes one minute to move one unit north, south, east, west, up or down. You cannot move diagonally and the maze is surrounded by solid rock on all sides.

Is an escape possible? If yes, how long will it take?
Input
The input consists of a number of dungeons. Each dungeon description starts with a line containing three integers L, R and C (all limited to 30 in size).
L is the number of levels making up the dungeon.
R and C are the number of rows and columns making up the plan of each level.
Then there will follow L blocks of R lines each containing C characters. Each character describes one cell of the dungeon. A cell full of rock is indicated by a ‘#’ and empty cells are represented by a ‘.’. Your starting position is indicated by ‘S’ and the exit by the letter ‘E’. There’s a single blank line after each level. Input is terminated by three zeroes for L, R and C.
Output
Each maze generates one line of output. If it is possible to reach the exit, print a line of the form
Escaped in x minute(s).

where x is replaced by the shortest time it takes to escape.
If it is not possible to escape, print the line
Trapped!
Sample Input
3 4 5
S…
.###.
.##…
###.#

##.##
##…

#.###
####E

1 3 3
S##
#E#

0 0 0

题意简介：假设你处在一个3D地牢，层数为L，每一层行为R，列为C。然后’S’代表入口，‘E’代表出口，’#‘代表墙壁，’.'代表可通口。然后让我们去寻找从入口到出口的最短逃逸时间，每移动一个单元格耗费一秒，若不能逃逸，则显示“Trapped！”。

解题思路：此题试求最短逃逸时间，显然我们不能用dfs去做，用dfs去做能够求解出几种逃脱方案，却不能用来求最短逃逸时间。那么，这题就是应该要用bfs搜索。为什么呢？为什么bfs搜索的到的是最短逃逸时间呢？bfs的原理是层次遍历，即同层次的点遍历完了才能遍历下一层，且因为这题每一步的代价是一样的（每走一步耗时一秒，如果代价不一样就不能用bfs）那既然是这样，即不同的路径都是同时出发同等代价的，那么先到达出口的即必为最短路径。我们利用一个三维数组作为地牢的存储结构，对于我们移动的操作，我们可以利用一个二维数组go[6][3]来代替。同时，我们也要利用一个辅助数组visited来避免重复访问。我们还要定义一个结构体node来储存坐标和当前的步数，显然起点时0，根据起点不断更新接下来的步数。bfs的核心就是利用队列先进先出的原理实现层次遍历，我们可以利用C++STL中的queue类来简单实现。

那么，我们直接看AC代码吧！（我加了很多注释，若还有疑问可以在评论区留言，有错误也请指出。）

#include <cstdio>
#include<iostream>
#include<memory.h>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstdlib>
#include<iterator>
#include<cstring>

using namespace std;

int go[6][3]={{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1},};//六个步骤，分别代表六个方向。
int l,r,c;//l为地牢高度，r和c分别代表行和列。
const int maxn=32;
char dungeon[maxn][maxn][maxn];//地牢
bool visited[maxn][maxn][maxn];//辅助数组，判断某点是否被访问过。
typedef struct node
{
	int x,y,z;//坐标。
	int step; //所花步数。
}node;
int start_x,start_y,start_z;//起点位置。
int end_x,end_y,end_z;//终点位置。
int i,j,k;//循环控制变量。
bool check(int x,int y,int z)
{
	if(x<0||x>=l||y<0||y>=r||z<0||z>=c)//判断该点是否越界
	return true;
	else if(visited[x][y][z])//判断该点有没有走过。
	return true;
	else if(dungeon[x][y][z]=='#')// 判断是否被岩石挡住了
	return true;
	return false;
}
int bfs()
{
	queue<node> Q;    //创建队列，实现先进先出的需求
	node temp,head;   //head每次存储队头元素,temp临时变量
	head.x=start_x;head.y=start_y;head.z=start_z;
	head.step=0;         //起点步数初始值为0
	Q.push(head);       //将起点入队
	while(!Q.empty())
	{
		head=Q.front();
		if(head.x==end_x&&head.y==end_y&&head.z==end_z)
			return head.step;
		Q.pop();
		for(int i=0;i<6;i++)
		{
			//改变坐标。
			temp.x=head.x+go[i][0];
			temp.y=head.y+go[i][1];
			temp.z=head.z+go[i][2];
			//判断该点是否合法。
			if(check(temp.x,temp.y,temp.z))continue;//非法。
			temp.step=head.step+1;
			visited[temp.x][temp.y][temp.z]=true;
			Q.push(temp);
		}
	}
	return 0;
}
int main()
{
	while(cin>>l>>r>>c)
	{
		if(l==0&&r==0&&c==0)break;
		for(int i=0;i<l;i++)
		{
			for(int j=0;j<r;j++)
			{
				cin>>dungeon[i][j];
				for(int k=0;k<c;k++)
				{
					if(dungeon[i][j][k]=='S')//保存入口坐标。
					{
						start_x=i;
						start_y=j;
						start_z=k;
					}
					else if(dungeon[i][j][k]=='E')//保存出口坐标
					{
						end_x=i;
						end_y=j;
						end_z=k;
					}
				}
			}
		}
		memset(visited,false,sizeof(visited));//初始化辅助数组。
		int result=bfs();
		if(result)
		{
			cout<<"Escaped in "<<result<<" minute(s)."<<endl;
		}
		else cout<<"Trapped!"<<endl;
	}
	return 0;
}

测试用例结果如下图：

无误。