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 5S…..###..##..###.#############.####…###########.#######E1 3 3S###E####0 0 0

Sample Output

Escaped in 11 minute(s).

Trapped!

题目解析

这道题首先要理解题意，它其实就是一个走迷宫的问题，可以采用dfs和bfs的做法。当人处于某一层时，他只能向左，向右，向上，向下走，#相当于墙，那么从起点开始，通过bfs遍历看此人能否到达终点，需要明确的是当人处在当前层位置时，他可以跳到下一层任意一行。但是跳到下一层所处的位置列数必须相同，就比如上面例子S向右走4步，向下走2步，向左走1步，向下走1步，现在S处于第一层的第四行第四列。然后S直接跳到了第二层的第四行第四列，1，S向右走1步，然后S直接跳到第三层终点1。于是S最少走的路为：4+2+1+1+1+1+1=11

Codes

#include
   
    #include
    
     using namespace std;char g[35][35][35]; int vis[35][35][35],dis[6][3]={
   {
   0,0,1},{
   0,0,-1},{
   0,-1,0},{
   0,1,0},{
   1,0,0},{
   -1,0,0}};int l,r,c;struct graph{
   	int x,y,z,len;}; graph gh;queue
     
       q;void bfs(){
   	vis[gh.z][gh.x][gh.y]=1;	q.push(gh);	while(!q.empty()){
   		gh=q.front();		q.pop();		if(g[gh.z][gh.x][gh.y]=='E'){
   			cout<<"Escaped in "<
      
       <<" minute(s).\n";			return;		}		for(int i=0;i<6;i++){
   			graph now;			now.z=gh.z+dis[i][0];			now.x=gh.x+dis[i][1];			now.y=gh.y+dis[i][2];			now.len=gh.len;			if(g[now.z][now.x][now.y]!='#'&&now.z>=0&&now.z
       
        =0&&now.x
        
         =0&&now.y
         
          >l>>r>>c){ if(l==0&&r==0&&c==0) break; while(!q.empty()) q.pop(); for(int i=0;i
          
           >g[i][j]; for(int k=0;k