Week12 B - 必做题 - 2

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

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

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

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

Sample Input

3 4 5
S….
.###.
.##..
###.#

#####
#####
##.##
##…

#####
#####
#.###
####E

1 3 3
S##
#E#
###

0 0 0

Sample Outpu

Escaped in 11 minute(s).
Trapped!

解题思路
三维的走迷宫
用SPFA找出最短路径
确保找的位置不超出范围 >=1 <=r
Code

#include<iostream>
#include<string.h>
#include<queue>
using namespace std;

int l,r,c;
int  s[40][40][40];
int sw[40][40][40];
int  sx[]={0,0,1,0,0,-1};
int  sy[]={0,1,0,0,-1,0};
int  sz[]={1,0,0,-1,0,0};
struct st{
	int x,y,z;
	st(int a1,int a2,int a3){
		x=a1,y=a2,z=a3;
	}
};
queue <st> q;
void find(int xa,int ya,int za){
    sw[xa][ya][za]=1;
    while(!q.empty()){
    	q.pop();
	}
	st first(xa,ya,za);
	q.push(first);
	while(!q.empty()){
		st now=q.front();
		q.pop();
		for(int i=0;i<6;i++){
			int tx=now.x+sx[i],ty=now.y+sy[i],tz=now.z+sz[i];
			if(s[tx][ty][tz]!=0&&sw[tx][ty][tz]==0&&tx>=1&&ty>=1&&tz>=1&&tx<=r&&ty<=c&&tz<=l){
				s[tx][ty][tz]=s[now.x][now.y][now.z]+1;
				sw[tx][ty][tz]=1;
				st next(tx,ty,tz);
				q.push(next);
			}
		}
	}
}


int main(){
	while(cin>>l>>r>>c){
		if(l==0&&r==0&&c==0){
			break;
		}
	memset(s,0,sizeof(s));
	memset(sw,0,sizeof(sw));
	int xs,ys,zs;
	int xe,ye,ze;
	char sin;
	for(int i=0;i<=l+1;i++){
		for(int j=0;j<=r+1;j++){
			for(int k=0;k<=c+1;k++){
				if(i==0||j==0||k==0||i==l+1||j==r+1||k==c+1){
					s[j][k][i]=0;
				}else{
					cin>>sin;
					if(sin=='S'){
						s[j][k][i]=0;
						xs=j,ys=k,zs=i;
					}else if(sin=='E'){
						s[j][k][i]=1;
						xe=j,ye=k,ze=i;
					}else if(sin=='#'){
						s[j][k][i]=0;
					}else if(sin=='.'){
						s[j][k][i]=1;
					}
				}
			}
		}
	}
	/*for(int i=0;i<=l+1;i++){
		for(int j=0;j<=r+1;j++){
			for(int k=0;k<=c+1;k++){
				cout<<s[j][k][i];
			}cout<<endl;
		}cout<<endl;
	}*/
	
	find(xs,ys,zs);
	if(sw[xe][ye][ze]==1){
		cout<<"Escaped in "<<s[xe][ye][ze]<<" minute(s)."<<endl;
	}else{
	    cout<<"Trapped!"<<endl;
	}
	//cout<<ans<<endl;
	
	}
	
	
	
}