ZeroJudge 解題筆記：c124. 00532 - Dungeon Master

作者：王一哲
日期：2026年3月16日


ZeroJudge 題目連結：c124. 00532 - Dungeon Master

解題想法

這題可以用一個三維陣列儲存地圖及步數，0 代表起點、障礙物、邊界，-1 代表還沒有走過的格子，另外在地圖的邊緣加一圈 0 當作哨兵，避免在用 BFS 找最短路徑時出界。 由於測資中有一些多餘的空行，用 Python 解題時可以用 sys.stdin.read().split() 一次讀取所有測資、拆開、存入串列，這樣可以很方便地避開空行。

Python 程式碼

使用時間約為 52 ms，記憶體約為 4.2 MB，通過測試。

import sys
from collections import deque

result = []
data = sys.stdin.read().split()
ptr = 0
while ptr < len(data):
    L, R, C = map(int, data[ptr:ptr+3])  # 迷宮的高、深、寬，對應 z、y、x 座標
    ptr += 3
    if L == 0 and R == 0 and C == 0: break  # 中止迴圈的條件
    sx, sy, sz, ex, ey, ez = 0, 0, 0, 0, 0, 0  # 起點、終點座標
    maze = [[[0]*(C+1) for _ in range(R+1)] for _ in range(L+1)]  # 迷宮，0 是起點、邊界、石頭
    """ 讀取地圖資料，-1 代表還沒有走過 """
    for z in range(L):  # 依序讀取 L 層地圖
        for y in range(R):  # 讀取 R 列地圖
            line = data[ptr]
            ptr += 1
            for x, ch in enumerate(line):  # 依序讀取此列的字元
                if ch == 'S':  # 起點，步數為 0
                    sz, sy, sx = z, y, x
                    maze[z][y][x] = 0
                elif ch == 'E':  # 終點，-1 代表還沒有走過
                    ez, ey, ex = z, y, x
                    maze[z][y][x] = -1
                elif ch == '.':  # 走道，-1 代表還沒有走過
                    maze[z][y][x] = -1
    """ BFS 找最短路徑 """
    que = deque([(sz, sy, sx)])  # que 放入起點
    find_ans = False  # 是否有解
    while que and not find_ans:  # 如果 que 還有資料而且還沒有找到答案，繼續執行
        z, y, x = que.popleft()  # 取出 que 最前面的資料
        for dz, dy, dx in ((1, 0, 0), (-1, 0, 0), (0, 1, 0), (0, -1, 0), (0, 0, 1), (0, 0, -1)):  # 6 方位檢查
            nz, ny, nx = z+dz, y+dy, x+dx  # 要檢查 (nz, ny, nx)
            if maze[nz][ny][nx] != -1: continue  # 如果此格不是 -1，找下一格
            maze[nz][ny][nx] = maze[z][y][x] + 1  # 設定此格步數
            if nz == ez and ny == ey and nx == ex:  # 走到終點，找到答案，中止迴圈
                find_ans = True
                break
            que.append((nz, ny, nx))  # (nz, ny, nx) 加入 que
    """ End of BFS """
    if find_ans:
        result.append(f"Escaped in {maze[ez][ey][ex]:d} minute(s).\n")
    else:
        result.append("Trapped!\n")
sys.stdout.write("".join(result))

C++ 程式碼

使用時間約為 1 ms，記憶體約為 528 kB，通過測試。

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

struct Point {
    int x, y, z;
};

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int L, R, C;  // 迷宮的高、深、寬，對應 z、y、x 座標
    while(cin >> L >> R >> C && (L != 0 || R != 0 || C != 0)) {
        int sx = 0, sy = 0, sz = 0, ex = 0, ey = 0, ez = 0;  // 起點、終點座標
        vector<vector<vector<int>>> maze (L+2, vector<vector<int>> (R+2, vector<int> (C+2, 0)));  // 迷宮，0 是起點、邊界、石頭
        /* 讀取地圖資料，-1 代表還沒有走過 */
        string line;  // 暫存一列地圖資料
        for(int z=1; z<=L; z++) {  // 依序讀取 L 層地圖
            for(int y=1; y<=R; y++) {  // 讀取 R 列地圖
                cin >> line;
                for(int x=1; x<=C; x++) {  // 讀取 C 個字元
                    char ch = line[x-1];
                    if (ch == 'S') {  // 起點，步數為 0
                        sz = z; sy = y; sx = x;
                        maze[z][y][x] = 0;
                    } else if (ch == 'E') {  // 終點，-1 代表還沒有走過
                        ez = z; ey = y; ex = x;
                        maze[z][y][x] = -1;
                    } else if (ch == '.') {  // 走道，-1 代表還沒有走過
                        maze[z][y][x] = -1;
                    }
                }
            }
        }
        /* BFS 找最短路徑 */
        Point start;
        start.x = sx; start.y = sy; start.z = sz;
        queue<Point> que; que.push(start);  // que 放入起點
        bool find_ans = false;  // 是否有解
        // 6 方位檢查用的位移量
        int dz[6] = {1, -1, 0, 0, 0, 0}, dy[6] = {0, 0, 1, -1, 0, 0}, dx[6] = {0, 0, 0, 0, 1, -1};
        while(!que.empty() && !find_ans) {  // 如果 que 還有資料而且還沒有找到答案，繼續執行
            int z = que.front().z, y = que.front().y, x = que.front().x;
            que.pop();  // 取出 que 最前面的資料
            for(int i=0; i<6; i++) {
                int nz = z+dz[i], ny = y+dy[i], nx = x+dx[i];  // 要檢查 (nz, ny, nx)
                if (maze[nz][ny][nx] != -1) continue;  // 如果此格不是 -1，找下一格
                maze[nz][ny][nx] = maze[z][y][x] + 1;  // 設定此格步數
                if (nz == ez && ny == ey && nx == ex) {  // 走到終點，找到答案，中止迴圈
                    find_ans = true;
                    break;
                }
                Point nxt; nxt.x = nx; nxt.y = ny; nxt.z = nz;
                que.push(nxt);  // nxt 加入 que
            }
        }
        /* End of BFS，印出答案 */
        if (find_ans) cout << "Escaped in " << maze[ez][ey][ex] << " minute(s).\n";
        else cout << "Trapped!\n";
    }
    return 0;
}