【Week12作业 B】必做题-2【模拟】

题意：

zjm被困在一个三维的空间中,现在要寻找最短路径逃生！
空间由立方体单位构成。
zjm每次向上下前后左右移动一个单位需要一分钟，且zjm不能对角线移动。
空间的四周封闭。zjm的目标是走到空间的出口。
是否存在逃出生天的可能性？如果存在，则需要多少时间？

输入第一行是一个数表示空间的数量。
每个空间的描述的第一行为L，R和C（皆不超过30）。
L表示空间的高度，R和C分别表示每层空间的行与列的大小。
随后L层，每层R行，每行C个字符。
每个字符表示空间的一个单元。’#‘表示不可通过单元，’.‘表示空白单元。
zjm的起始位置在’S’，出口为’E’。每层空间后都有一个空行。
L，R和C均为0时输入结束。

每个空间对应一行输出。
如果可以逃生，则输出如下
Escaped in x minute(s).
x为最短脱离时间。

如果无法逃生，则输出如下
Trapped!

思路：

在三维迷宫中寻找起点到终点的最短路。用bfs来求解。从起点开始bfs，每从队列中取出一个坐标，搜索它上下前后左右六个坐标，如果没有访问过，则将其加入队列，该坐标到起点的距离为上一个坐标的距离+1。bfs完后数组中存有所有坐标到起点的距离。如果没有到达终点，则输出Trapped!，否则输出距离。

总结：

一道三维迷宫求起点终点最短路问题。在二维bfs上进行拓展即可解答。

代码：

#include <iostream>
#include <queue>
using namespace std;

int L,R,C;
int a[31][31][31];
bool vis[31][31][31];
int bx,by,bz,ex,ey,ez;	//起点与终点 
//上下前后左右 
int dx[]={0,0,1,-1,0,0};
int dy[]={0,0,0,0,1,-1};
int dz[]={1,-1,0,0,0,0};
struct point
{
	int x,y,z;
	point(int x1,int y1,int z1)
	{
		x=x1,y=y1,z=z1;
	}
};
queue<point> v;
void solve()
{
	vis[bx][by][bz]=1;
	while(!v.empty())
		v.pop();
	point thePoint(bx,by,bz);
	v.push(thePoint);
	while(!v.empty())
	{
		point now=v.front();
		v.pop();
		for(int i=0;i<6;i++)
		{
			int nx=now.x+dx[i],ny=now.y+dy[i],nz=now.z+dz[i];
			if(nx>=1&&nx<=R&&ny>=1&&ny<=C&&nz>=1&&nz<=L)
			{
				if(a[nx][ny][nz]!=0&&vis[nx][ny][nz]==0)
				{
					a[nx][ny][nz]=a[now.x][now.y][now.z]+1;
					vis[nx][ny][nz]=1;
					point nextPoint(nx,ny,nz);
					v.push(nextPoint);
				}
			}
		}
	} 
	if(vis[ex][ey][ez]==1)
		cout<<"Escaped in "<<a[ex][ey][ez]<<" minute(s)."<<endl;
	else 
		cout<<"Trapped!"<<endl;
}
int main()
{
	while(1)
	{
		cin>>L>>R>>C;
		if(L==0&&R==0&&C==0)
			break;
		for(int i=1;i<=L;i++)
			for(int j=1;j<=R;j++)
				for(int k=1;k<=C;k++)
				{
					char ch;
					cin>>ch;
					if(ch=='#')
						a[j][k][i]=0;
					else if(ch=='.')
						a[j][k][i]=1;
					else if(ch=='S')
					{
						a[j][k][i]=0;
						bx=j,by=k,bz=i;
					}
					else if(ch=='E')
					{
						a[j][k][i]=1;
						ex=j,ey=k,ez=i;
					}
				}
		for(int i=0;i<31;i++)
			for(int j=0;j<31;j++)
				for(int k=0;k<31;k++)
					vis[i][j][k]=0;
		solve();
	}
}