解题思路

这道题是一个典型的 三维迷宫最短路径问题，可以使用 广度优先搜索（BFS） 来解决。由于每次移动（上下、左右、前后）的代价相同（1分钟），BFS 可以保证第一次到达终点时的路径就是最短路径。

关键步骤

1. 输入处理

   • 读取层数 L、行数 R 和列数 C。
   • 读取三维地牢数据，记录起点 S 和终点 E 的坐标。

2. BFS 初始化

   • 使用队列存储待访问的坐标 (l, r, c) 和当前步数 step。
   • 使用 visited[l][r][c] 记录是否访问过该位置，避免重复访问。

3. BFS 遍历

   • 每次从队列取出当前位置，检查是否是终点 E，如果是则返回当前步数。
   • 否则，向 6 个方向（上下、左右、前后） 扩展，如果该位置可通行（. 或 E）且未被访问，则加入队列。

4. 终止条件

   • 如果队列为空仍未找到终点，说明无法逃脱，返回 Trapped!。

C++ 代码实现

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

int L, R, C;
char dungeon[35][35][35];
int visited[35][35][35];

// 6个移动方向：上下、左右、前后
int dl[] = {1, -1, 0, 0, 0, 0};
int dr[] = {0, 0, 1, -1, 0, 0};
int dc[] = {0, 0, 0, 0, 1, -1};

struct Point {
    int l, r, c, step;
    Point(int l, int r, int c, int step) : l(l), r(r), c(c), step(step) {}
};

int bfs(int sl, int sr, int sc) {
    queue<Point> q;
    q.push(Point(sl, sr, sc, 0));
    visited[sl][sr][sc] = 1;

    while (!q.empty()) {
        Point cur = q.front();
        q.pop();

        if (dungeon[cur.l][cur.r][cur.c] == 'E') {
            return cur.step;
        }

        for (int i = 0; i < 6; i++) {
            int nl = cur.l + dl[i];
            int nr = cur.r + dr[i];
            int nc = cur.c + dc[i];

            if (nl >= 0 && nl < L && nr >= 0 && nr < R && nc >= 0 && nc < C) {
                if (!visited[nl][nr][nc] && dungeon[nl][nr][nc] != '#') {
                    visited[nl][nr][nc] = 1;
                    q.push(Point(nl, nr, nc, cur.step + 1));
                }
            }
        }
    }
    return -1; // 无法逃脱
}

int main() {
    while (cin >> L >> R >> C && (L || R || C)) {
        memset(visited, 0, sizeof(visited));
        int sl, sr, sc;

        for (int l = 0; l < L; l++) {
            for (int r = 0; r < R; r++) {
                string line;
                cin >> line;
                for (int c = 0; c < C; c++) {
                    dungeon[l][r][c] = line[c];
                    if (dungeon[l][r][c] == 'S') {
                        sl = l;
                        sr = r;
                        sc = c;
                    }
                }
            }
            // 跳过每个层描述后的空行
            string emptyLine;
            getline(cin, emptyLine); // 读取剩余的部分
            getline(cin, emptyLine); // 读取空行
        }

        int ans = bfs(sl, sr, sc);
        if (ans != -1) {
            cout << "Escaped in " << ans << " minute(s)." << endl;
        } else {
            cout << "Trapped!" << endl;
        }
    }
    return 0;
}