POJ 2251 Dungeon Master：三維 BFS 迷宮逃脫最短路徑

題目大意

三維迷宮 L×R×C (≤ 30)，S 起點，E 終點，# 牆，. 空地。六個方向移動（上下左右前後），每步 1 分鐘。求最短逃脫時間或判斷無法逃脫。

三維 BFS 模板

狀態：(z, x, y, time)。
方向數組：dz[6]={0,0,0,0,1,-1}, dx[6]={1,-1,0,0,0,0}, dy[6]={0,0,1,-1,0,0}。
訪問標記 vis[L][R][C]。

核心代碼

struct Node { int z, x, y, t; };
int bfs() {
    queue q;
    q.push({sz, sx, sy, 0});
    vis[sz][sx][sy] = 1;
    while (!q.empty()) {
        Node cur = q.front(); q.pop();
        if (cur.z == ez && cur.x == ex && cur.y == ey) return cur.t;
        for (int i = 0; i < 6; ++i) {
            int nz = cur.z + dz[i], nx = cur.x + dx[i], ny = cur.y + dy[i];
            if (nz < 0 || nz >= L || nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
            if (vis[nz][nx][ny] || maze[nz][nx][ny] == '#') continue;
            vis[nz][nx][ny] = 1;
            q.push({nz, nx, ny, cur.t + 1});
        }
    }
    return -1;  // Trapped
}

關鍰細節

1. 輸入格式：每層 R 行，層間有空行。用 scanf("%s", ...) 逐行讀取自動跳過空白。
2. 座標映射：代碼中 z 對應層，x 對應行，y 對應列，務必與輸入循環一致。
3. 輸出格式：Escaped in %d minute(s). 或 Trapped!，注意句點與驚嘆號。
4. 多測試用例：直到 L=R=C=0 結束。

常見錯誤（血淚教訓）

• 三維數組下標順序搞混（如 map[z][x][y] vs map[x][y][z]）。
• 循環變量寫錯（如 for(i=0;i 裡用 i++ 代替 j++）。
• 忘記標記起點已訪問，導致重複入隊。
• 輸出格式空格/標點不符導致 WA。