Description - 题目描述

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

Input - 输入

输入第一行是一个数表示空间的数量。
每个空间的描述的第一行为L，R和C（皆不超过30）。
L表示空间的高度。
R和C分别表示每层空间的行与列的大小。
随后L层地牢，每层R行，每行C个字符。
每个字符表示空间的一个单元。'#'表示不可通过单元，'.'表示空白单元。你的起始位置在'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 Output - 输出样例

Escaped in 11 minute(s).
Trapped!

题解：

        就是在三维空间里进行bfs，方向变为六个方向

代码：

#include <stdio.h>

#include <algorithm>
#include <math.h>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <string.h>
#include <iostream>
#include <vector>
#include <functional>

using namespace std;

int l,r,c;
int ex,ey,ez;
char ma[35][35][35];
int dir[6][3]={{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
int vis[35][35][35];

struct node
{
    int z,x,y,step;
    friend bool operator<(node a,node b)
    {
        return a.step>b.step;
    }
};

bool check(int z,int x,int y)
{
    if(z>=0&&z<l&&x>=0&&x<r&&y>=0&&y<c&&vis[z][x][y]==0&&ma[z][x][y]!='#')
        return 1;
    return 0;
}

int bfs(int z,int x,int y)
{
    priority_queue<node> q;
    node now,next;
    now.z=z;
    now.x=x;
    now.y=y;
    now.step=0;
    vis[now.z][now.x][now.y]=1;
    q.push(now);
    while(!q.empty())
    {
        now=q.top();
        q.pop();
        if(ma[now.z][now.x][now.y]=='E')
        {
            return now.step;
        }
        for(int i=0;i<6;i++)
        {
            next.z=now.z+dir[i][0];
            next.x=now.x+dir[i][1];
            next.y=now.y+dir[i][2];
            if(check(next.z,next.x,next.y))
            {
                vis[next.z][next.x][next.y]=1;
                next.step=now.step+1;
                q.push(next);
            }
        }
    }
    return -1;
}
int main()
{
    while(~scanf("%d%d%d",&l,&r,&c))
    {
        if(l==0&&r==0&&c==0) break;
        memset(vis,0,sizeof(vis));
        for(int i=0;i<l;i++)
        {
            getchar();
            for(int j=0;j<r;j++)
            {
                for(int k=0;k<c;k++)
                {
                    scanf("%c",&ma[i][j][k]);
                    if(ma[i][j][k]=='S')
                    {
                        ez=i;
                        ex=j;
                        ey=k;
                    }
                }
                getchar();
            }
            
        }
        int ans=bfs(ez,ex,ey);
        if(ans==-1)
            cout<<"Trapped!"<<endl;
        else
            cout<<"Escaped in "<<ans<<" minute(s)."<<endl;    
    }
    return 0;
}