Description:

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

Sample Output:

3

题目链接

这道题比普通的bfs搜索多了一个维度，但是其实做法还是一样，把数组开为三维存储坐标信息，搜索的时候用三层循环搜索六个方向。

AC代码:

#include <stdio.h>
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <cstdlib>
#include <sstream>

using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 32;

// 地牢“地形”
char maze[maxn][maxn][maxn];
int L,R,C;
// 起点左边
int sx,sy,sz;
// 终点坐标
int gx,gy,gz;
// d[i][j][k]数组记录起点到达x=i,y=j,z=k坐标时所需要的步数
int d[maxn][maxn][maxn];
// 三个数组改变坐标进行周边六个方向搜索
int dx[6] = {1,-1,0,0,0,0}, dy[6] = {0,0,0,0,1,-1}, dz[6] = {0,0,1,-1,0,0};

// 结构体存储坐标
struct site {
    int a;
    int b;
    int c;
};

// 宽度优先搜索
void bfs() {
    // 建立搜索队列
    queue<site> que;
    // 将所有坐标步数初始化为正无穷
    mem(d, INF);
    // 向搜索队列中加入起点
    site q;
    q.a = sz,q.b = sx,q.c = sy;
    que.push(q);
    // 将起点步数存为0
    d[sz][sx][sy] = 0;
    // 当搜索队列中不为空时持续按照队列进行搜索
    while (que.size()) {
        // 取出队首元素搜索
        site p = que.front();
        que.pop();
        // 如果取出元素为终点则停止搜索
        if (p.a == gz && p.b == gx && p.c == gy) {
            break;
        }
        // 否则在取出元素的六个可移动方向进行搜索
        for (int i = 0;i < 6;++i) {
            // 搜索到新坐标
            int nz = p.a + dz[i],nx = p.b + dx[i],ny = p.c + dy[i];
            // 如果坐标在地牢范围内&&不是岩石单位&&没有被搜索过,则将此坐标添加至搜索队列
            if (0 < nz && nz <= L && 0 < nx && nx <= R && 0 < ny && ny <= C && maze[nz][nx][ny] != '#' && d[nz][nx][ny] == INF) {
                site tianjia;
                tianjia.a = nz;
                tianjia.b = nx;
                tianjia.c = ny;
                que.push(tianjia);
                // 到达此点的步数为此循环中在队列中取出元素步数+1
                d[nz][nx][ny] = d[p.a][p.b][p.c] + 1;
            }
        }
    }
}

int main() {
    // 加速输入输出
    ios::sync_with_stdio(0);
    cin.tie(0);
    // 输入地牢范围
    while (cin >> L >> R >> C,L,R,C) {
        // 输入地牢“地形”
        for (int i = 1;i <= L;++i) {
            for (int j = 1;j <= R;++j) {
                for (int k = 1;k <= C;++k) {
                    cin >> maze[i][j][k];
                    // 确定起点位置
                    if (maze[i][j][k] == 'S') {
                        sz = i;
                        sx = j;
                        sy = k;
                    }
                    // 确定终点位置
                    if (maze[i][j][k] == 'E') {
                        gz = i;
                        gx = j;
                        gy = k;
                    }
                }
            }
        }
        // 宽度优先搜索
        bfs();
        // 如果从起点到达终点位置的步数为正无穷说明无法到达，否则输出步数
        // 按照题目要求输出
        if (d[gz][gx][gy] == INF) {
            cout << "Trapped!" << endl;
        }
        else {
            cout << "Escaped in " << d[gz][gx][gy] << " minute(s)." << endl;
        }
    }
    return 0;
}