POJ 2251 / UVA 532：三維迷宮 BFS 最短路徑

問題描述

L 層、R 行、C 列的三維迷宮，'S' 起點、'E' 終點、'#' 牆壁、'.' 通路。求最短逃脫時間（每步 1 分鐘），不可達輸出 "Trapped!"。

解法：三維 BFS

• 狀態：(x, y, z, depth)。
• 6 方向向量：上下層、四向平面。
• 訪問陣列 `vis[40][40][40]`。
• 隊列標準 BFS，遇到 'E' 即返回 depth+1。

核心代碼

#include 
#include 
#include 
#include 
using namespace std;

int L, R, C, Sx, Sy, Sz;
char maze[40][40][40];
int dir[6][3] = {{-1,0,0},{1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
int vis[40][40][40];

struct Node { int x, y, z, d; };

bool valid(int x, int y, int z) {
    return x>=0 && x=0 && y=0 && z q;
    memset(vis, 0, sizeof(vis));
    q.push({sx, sy, sz, 0});
    vis[sx][sy][sz] = 1;
    while (!q.empty()) {
        Node cur = q.front(); q.pop();
        for (int i = 0; i < 6; i++) {
            int nx = cur.x + dir[i][0];
            int ny = cur.y + dir[i][1];
            int nz = cur.z + dir[i][2];
            if (valid(nx, ny, nz) && !vis[nx][ny][nz] && maze[nx][ny][nz] != '#') {
                if (maze[nx][ny][nz] == 'E') return cur.d + 1;
                vis[nx][ny][nz] = 1;
                q.push({nx, ny, nz, cur.d + 1});
            }
        }
    }
    return -1;
}

int main() {
    while (scanf("%d%d%d", &L, &R, &C), L||R||C) {
        memset(vis, 0, sizeof(vis));
        for (int i = 0; i < L; i++)
            for (int j = 0; j < R; j++)
                for (int k = 0; k < C; k++) {
                    cin >> maze[i][j][k];
                    if (maze[i][j][k] == 'S') { Sx=i; Sy=j; Sz=k; }
                }
        int ans = bfs(Sx, Sy, Sz);
        if (ans != -1) printf("Escaped in %d minute(s).\n", ans);
        else printf("Trapped!\n");
    }
    return 0;
}

注意事項

• 輸入以 `0 0 0` 結束。
• 字符讀取用 `cin >>` 自動跳過空白，避免換行符干擾。
• 方向向量順序不影響 BFS 正確性。