ZeroJudge 解題筆記：c134. 00668 - Parliament

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


ZeroJudge 題目連結：c134. 00668 - Parliament

解題想法

這題要將某個正整數 n，分拆成任意個不重複的正整數，使分拆後的正整數乘積最大。因為拆成 1 不會使乘積變大，至少從 2 開始分拆，盡量拆成越多個數字越好。如果 $n \leq 4$ 分拆後的正整數乘積不會大於 $n$，因此題目的測資 $\geq 5$ 。分拆時從 $i=2$ 開始測試，每次分拆後將 $n-i$，直到 $n < i$ 為止，如果最後 $n > 0$ ，再將分拆出來最大的 $n$ 個數都加 1。 注意：此題的答案只要輸出分拆後的正整數，不需要輸出個數。題目敘述與測資的要求不合。

Python 程式碼

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

def solve():
    import sys
    
    result = []
    data = sys.stdin.read().split()
    T = int(data[0])
    ptr = 1
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        if result:  # 不是第一組測資，先換行
            result.append("\n")
        if n <= 4:  # 特例，小於等於 4，不能分拆
            result.append(f"{n:d}\n")
        else:
            i = 2  # 從 2 開始測試
            ans = []  # 分拆的數字
            while n >= i:  # 如果 n 還能分拆
                ans.append(i)  # i 加入 anss
                n -= i  # n 減去 i
                i += 1  # i 加 1
            for j in range(len(ans)-1, len(ans)-n-1, -1):  # 最後 n 個數加 1
                ans[j] += 1
            res = " ".join(map(str, ans))
            result.append(f"{res}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：c133. 00639 - Don't Get Rooked

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


ZeroJudge 題目連結：c133. 00639 - Don't Get Rooked

解題想法

這題很像八皇后，用集合 rooks 儲存已經放置城堡的位置，寫一個自訂函式 is_safe 檢查代入的位置 (row, col) 是否安全；再寫另一個自訂函式 backtrack 代入 (0, 0)，用遞迴與回溯找答案。

Python 程式碼

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

import sys

def solve(n):
    grid = [list(sys.stdin.readline().strip()) for _ in range(n)]
    rooks = set()  # 已放置城堡的位置
    ans = 0  # 答案
    """ grid[row][col] 處是否可以放置城堡 """
    def is_safe(row, col):
        for r in range(row-1, -1, -1):  # 向上檢查
            if grid[r][col] == 'X': break
            if (r, col) in rooks: return False
        for r in range(row+1, n, 1):  # 向下檢查
            if grid[r][col] == 'X': break
            if (r, col) in rooks: return False
        for c in range(col-1, -1, -1):  # 向左檢查
            if grid[row][c] == 'X': break
            if (row, c) in rooks: return False
        for c in range(col+1, n, 1):  # 向右檢查
            if grid[row][c] == 'X': break
            if (row, c) in rooks: return False
        return True  # 通過 4 個方向的檢查，回傳 True
    """ 回溯，代入 row, col """
    def backtrack(row, col):
        nonlocal ans  # 這樣才能修改函數外的變數值
        if col == n:  # 如果欄已經出界
            col = 0   # 歸零
            row += 1  # 找下一列
        if row == n:  # 如果列已經出界
            ans = max(ans, len(rooks))  # 更新答案
            return    # 遞迴出口
        # 測試 (row, col) 是否可以放置城堡
        if grid[row][col] == '.' and is_safe(row, col):
            rooks.add((row, col))  # 放置城堡
            backtrack(row, col+1)  # 遞迴，測試下一欄是否能放置城堡
            rooks.remove((row, col))  # 回溯
        backtrack(row, col+1)  # 遞迴，不在 (row, col) 處放置城堡
    """ End of backtrack """
    backtrack(0, 0)  # 從 (0, 0) 開始測試
    return ans

result = []
for line in sys.stdin:
    if not line.strip(): continue
    n = int(line)
    if n == 0: break
    result.append(f"{solve(n):d}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：c131. 00615 - Is It A Tree?

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


ZeroJudge 題目連結：c131. 00615 - Is It A Tree?

解題想法

用自訂函式 test 代入節點資料，檢測是否為樹。檢測項目為

• 讀取邊的端點 $u, v$，因為 $u$ 可以連到 $v$，$u$ 為父節點，$v$ 為子節點。如果 $v$ 已經有父節點，因為一個節點不可能有兩個父節點，不是樹，回傳 False。
• 檢查是否只有一個根節點，因為不可能有兩個根節點。
• 用 BFS 從根節點開始走訪，如果能夠走到所有節點，是樹，回傳 True。

Python 程式碼

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

import sys
from collections import deque

def test(data):  # 檢測用的函式，輸入節點資料
    if data == [0, 0]: return True  # 特例，資料只有 0, 0，回傳 True
    parent, children = dict(), dict()  # {v: u} v 的父節點是 u，u 的子節點集合
    nodes = set()  # 所有節點的集合
    for i in range(0, len(data), 2):  # 一次讀取兩筆測資
        u, v = data[i], data[i+1]  # 節點 u 連到 v
        nodes.add(u); nodes.add(v)  # u, v 加入 nodes
        if v in parent: return False  # 如果 v 已經有父節點，回傳 True
        parent[v] = u  # v 的父節點是 u
        if u not in children: children[u] = {v}  # 如果 u 還沒有子節點，建立集合，加入 v
        else: children[u].add(v)  # 反之，直接加入 v
    ### 檢查是否只有一個根節點 ###
    root = -1  # 根節點
    for node in nodes:  # 依序讀取所有節點
        if node not in parent:  # 如果 node 沒有父節點
            if root == -1: root = node  # 如果 root 等於 -1，node 是根節點
            elif root != -1: return False  # 反之，不可能有兩個根節點，回傳 False
    ### BFS 檢查所有節點是否相連 ###
    que = deque([root])  # 待走訪佇列，先加入根節點
    visited = {node: False for node in nodes}  # 各節點走訪狀態
    visited[root] = True  # 已走訪根㿝3點
    while que:  # 如果 que 還有資料繼續執行
        u = que.popleft()  # 從 que 開頭取出資料
        if u not in children: continue  # 如果 u 沒有子節點，找下一個點
        for v in children[u]:  # 依序讀取 u 的子節點 v
            if visited[v]: return False  # 如果 v 已走訪，環狀結構，回傳 False
            visited[v] = True  # 已走訪 v
            que.append(v)  # v 加入 que
    ### End of BFS，如果所有節點已走訪回傳 True ###
    return all(visited.values())

"""" 讀取資料並解題 """
lines = sys.stdin.readlines()  # 讀取所有測資
idx = 0  # 從 lines 讀取資料的索引值
ca = 0  # 第幾組測資
result = []  # 要輸出的字串
while idx < len(lines):  # 如果 idx 還沒有出界繼續執行
    line = lines[idx]  # 讀取一行
    idx += 1
    line = line.strip()  # 跳過空行
    if not line: continue
    if line == "-1 -1": break  # 中止迴圈的條件
    ca += 1
    if line == "0 0":  # 特例，這組測資只有 0 0
        data = [0, 0]
    else:  # 其它狀況
        data = list(map(int, line.split()))  # 轉成整數串列
        if data[-1] == 0 and data[-2] == 0:  # 如果最後兩項都是 0
            data = data[:-2]  # 去掉最後兩項，結束這組測資
        else:  # 還有測資
            while True:  # 繼續讀取，直到結尾是 0 0 為止
                tmp = list(map(int, lines[idx].split()))
                idx += 1
                if tmp[-1] == 0 and tmp[-2] == 0:
                    data += tmp[:-2]
                    break
                else: data += tmp
    state = " " if test(data) else " not "  # 依照測試結果決定輸出的內容
    result.append(f"Case {ca:d} is{state:s}a tree.\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：c130. 00574 - Sum It Up

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


ZeroJudge 題目連結：c130. 00574 - Sum It Up

解題想法

這題考自訂函式的遞迴與回溯，同時用 set 儲存已經測試的過組合。

Python 程式碼

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

import sys

def solve(line):  # 解題用的函式
    nums = list(map(int, line.split()))  # 讀取一行測資
    t, n = nums[0], nums[1]  # 前兩項是目標、可用數字數量
    nums = nums[2:]  # 後面是可用的數字
    tested = set()  # 已測試過的組合，要用 tuple
    result = [f"Sums of {t:d}:\n"]  # 答案開頭
    """ 回溯，代入已選數字、加總、起點索引值 """
    def backtrack(choice, total, start):
        if tuple(choice) in tested: return  # 已測試過，遞迴出口
        tested.add(tuple(choice))  # choice 轉成 tuple 加入 tested
        if total > t: return  # 加總大於目標，遞迴出口
        if total == t:  # 加總等於目標，新增一組解，遞迴出口
            result.append("+".join(map(str, choice)) + "\n")
            return
        for i in range(start, n):  # 依序測試 nums[start] ~ nums[n-1]
            backtrack(choice + [nums[i]], total + nums[i], i+1)  # 選擇 nums[i]
            backtrack(choice, total, i+1)  # 不選擇 nums[i]
    """ End of backtrack """
    backtrack([], 0, 0)  # 呼叫 backtrack，代入空串列、加總 0、起點 0
    if len(result) == 1: result.append("NONE\n")  # 如果 result 長度為 1，加入 NONE
    sys.stdout.write("".join(result))  # 輸出答案

if __name__ == "__main__":
    for line in sys.stdin:
        line = line.strip()
        if not line: continue
        if line == "0 0": break
        solve(line)

ZeroJudge 解題筆記：c129. 00572 - Oil Deposits

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


ZeroJudge 題目連結：c129. 00572 - Oil Deposits

解題想法

這類連通區塊的題目用 BFS 就對了。但是這題的連通方式跟踩地雷一樣，有 8 個方向要檢查。

Python 程式碼

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

import sys
from collections import deque

for line in sys.stdin:
    if not line.strip(): continue
    m, n = map(int, line.split())  # 地圖尺寸 m*n
    if m == 0 and n == 0: break  # 中止迴圈
    grid = [list(sys.stdin.readline().strip()) + ['*'] for _ in range(m)]  # 地圖最右邊加 * 當作哨兵
    grid.append(['*']*(n+1))  # 地圖最下方加 * 當作哨兵
    cnt = 0  # 連通區域數量
    """ BFS """
    for i in range(m):  # 依序掃過地圖每一格，不包含哨兵
        for j in range(n):
            if grid[i][j] == '*': continue  # 不含石油，找下一格
            que = deque([(i, j)])  # 待走訪的佇列
            cnt += 1  # 數量加 1
            grid[i][j] = '*'  # 此格已走訪，設定為 *
            while que:  # 如果 que 有資料繼續執行
                r, c = que.popleft()  # 取出 que 最前面的資料
                # 注意，這題的連通方式跟踩地雷一樣，有 8 個方向要檢查
                for dr, dc in ((0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1)):
                    nr, nc = r+dr, c+dc  # 要檢查 (nr, nc)
                    if grid[nr][nc] == '*': continue  # 不含石油，找下一格
                    grid[nr][nc] = '*'  # 此格已走訪，設定為 *
                    que.append((nr, nc))  # (nr, nc) 加到 que
    """ End of BFS """
    sys.stdout.write(f"{cnt:d}\n")

ZeroJudge 解題筆記：c128. 00544 - Heavy Cargo

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


ZeroJudge 題目連結：c128. 00544 - Heavy Cargo

解題想法

這題跟 c125. 00534 - Frogger。 依序讀取兩座城市的名稱及道路的承受重量上限，城市之間連接的關係存入字典 graph，key 為城市的名稱，value 為連接的城市名稱，格式為 list；道路資料存入字典 edge，key 為兩座城市 $u, v$ 組成的 tupel，value 為重量，因為是無向圖，$(u, v), (v, u)$ 都要存資料。 開一個陣列 $ans$，儲存到達第 $i$ 座城市的路徑可以承受的最大重量的最小值。接下來用一個最大優先佇列 $pq$，資料為 $(重量, 城市名稱)$，代表到第 $i$ 座城市的路徑上某一條路可以承受的最大重量，重量大的資料放上面。因為 Python 的 heapq 是最小優先佇列，為了把最大值放在上面，重量要加負號。如果 $pq$ 還有資料，而且 $pq$ 最上面的城市不等於終點，while 迴圈繼續執行。每次取出 $pq$ 最上方的資料，目前的重量 $curr$、城市的名稱 $u$，掃過與 $u$ 相連的城市 $v$，取 $curr$ 與 $edge[u, v]$ 較小者為新的重量 $new_w$，如果 $new_w < ans[v]$，更新 $ans[v]$，並將 ${new_w, v}$ 加入 $pq$。

Python 程式碼

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

import sys, heapq

ca = 0
result = []
for line in sys.stdin:
    if not line.strip(): continue
    n, r = map(int, line.split())  # n 個城市，r 條道路
    if n == 0 and r == 0: break  # 中止迴圈的條件
    ca += 1  # 測資編號加 1
    graph, edge = dict(), dict()  # 城市連接的關係，道路可以承受的重量
    for _ in range(r):  # 讀取 r 條道路
        u, v, w = sys.stdin.readline().split()  # 城市 u、v 之間的道路可以承受重量 w
        w = int(w)  # w 轉成 int
        if u not in graph: graph[u] = [v]  # 如果 u 不在 graph 之中，設定為 [v]
        else: graph[u].append(v)  # 反之，加上 v
        if v not in graph: graph[v] = [u]  # 如果 v 不在 graph 之中，設定為 [u]
        else: graph[v].append(u)  # 反之，加上 u
        edge[u, v] = w  # u、v 之間的道路可以承受重量 w
        edge[v, u] = w
    ans = {k: 0 for k in graph.keys()}  # 走到每個城市的路上可以承受的重量最大值
    start, end = sys.stdin.readline().split()  # 起點、終點
    pq = [(-float('inf'), start)]  # (-重量, 城市)，加負號讓重量大的放上面
    while pq and pq[0][1] != end:  # 如果 pq 有資料而且最上面的城市不是終點
        w, u = heapq.heappop(pq)  # 取出 pq 最上面的重量、城市
        w = -w  # w 轉成正值
        for v in graph[u]:  # 依序取出 u 連接的城市 v
            new_w = min(w, edge[u, v])  # 取 w 與 u、v 之間可以承受重量較小者
            if new_w > ans[v]:  # 如果 new_w 是新的最大值
                ans[v] = new_w  # 更新 ans[v]
                heapq.heappush(pq, (-new_w, v))  # (-new_w, v) 加入 pq
    if ca > 1: result.append("\n")  # 如果不是第 1 筆測資，先換行
    result.append(f"Scenario #{ca:d}\n{ans[end]:d} tons\n")  # 答案加入 result
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：c127. 00537 - Artificial Intelligence

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


ZeroJudge 題目連結：c127. 00537 - Artificial Intelligence

解題想法

我用字典儲存前綴詞及單位對應的倍率，從讀取到的字串之中搜尋 I=、U=、P= 這 3 個字串，如果有找到這 3 個字串，再從字串索引值加 2 的位置開始向後讀取字元，找出對應的數字。最後配合前綴詞及單位調整數值的大小，輸出答案。

Python 程式碼

用時間約為 7 ms，記憶體約為 3 MB，通過測試。

prefix = {'m': 0.001, 'k': 1000, 'M': 1000000, 'A': 1, 'V': 1, 'W': 1}  # 前綴詞及單位對應的倍率
T = int(input())  # T 組測資
for t in range(1, T+1):  # t = 1 ~ T
    if t > 1: print()  # 如果不是第 1 組測資，先換行
    print(f"Problem #{t:d}")
    line = input()  # 讀取一行字串
    idx_I = line.find("I=")  # 從字串中找 I= 的索引值
    idx_U = line.find("U=")  # 從字串中找 U= 的索引值
    idx_P = line.find("P=")  # 從字串中找 P= 的索引值
    I, U, P = 0, 0, 0  # 電流、電壓、電功率量值
    if idx_I != -1:  # 字串中有 I=
        tmp = ""  # 暫存量值用的字串
        for c in line[idx_I+2:]:  # 從 idx_I+2 開始讀取字元
            if c.isnumeric() or c == '.': tmp += c   # 如果 c 是數字或小數點，c 加到 tmp
            else:  # 如果 c 是其它字元
                I = float(tmp)  # tmp 轉成浮點數存入 I
                I *= prefix[c]  # 乘以前綴詞對應的倍率
                break  # 中止迴圈
    if idx_U != -1:  # 字串中有 U=
        tmp = ""  # 暫存量值用的字串
        for c in line[idx_U+2:]:  # 從 idx_U+2 開始讀取字元
            if c.isnumeric() or c == '.': tmp += c   # 如果 c 是數字或小數點，c 加到 tmp
            else:  # 如果 c 是其它字元
                U = float(tmp)  # tmp 轉成浮點數存入 U
                U *= prefix[c]  # 乘以前綴詞對應的倍率
                break  # 中止迴圈
    if idx_P != -1:  # 字串中有 P=
        tmp = ""  # 暫存量值用的字串
        for c in line[idx_P+2:]:  # 從 idx_P+2 開始讀取字元
            if c.isnumeric() or c == '.': tmp += c   # 如果 c 是數字或小數點，c 加到 tmp
            else:  # 如果 c 是其它字元
                P = float(tmp)  # tmp 轉成浮點數存入 P
                P *= prefix[c]  # 乘以前綴詞對應的倍率
                break  # 中止迴圈
    ### 印出答案 ###
    if idx_I == -1: print(f"I={P/U:.2f}A")  # 求電流
    elif idx_U == -1: print(f"U={P/I:.2f}V")  # 求電壓
    elif idx_P == -1: print(f"P={I*U:.2f}W")  # 求電功率

ZeroJudge 解題筆記：c126. 00536 - Tree Recovery

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


ZeroJudge 題目連結：c126. 00536 - Tree Recovery

解題想法

這題需要知道二元樹的結構及走訪的順序。前序走訪的順序為父節點、左子節點、右子節點，中序走訪的順序為左子節點、父節點、右子節點，後序走訪的順序為左子節點、右子節點、父節點。因此，從測資中讀到的前序走訪資料開頭就是根節點，測資中的中序走訪資料左側為根節點的左子樹，右側為根節點的右子樹。依照這樣的原則設計從前序走訪、中序走訪資料建立後序走訪資料的函式。

Python 程式碼

用字串儲存二元樹走訪的資料，用時間約為 7 ms，記憶體約為 2.8 MB，通過測試。

import sys

def build_tree(preorder, inorder):
    if not preorder or not inorder: return ""  # 如果沒有資料，回傳空字串
    root = preorder[0]  # 前序走訪開頭為根節點
    root_idx = inorder.find(root)  # 找到中序走訪資料中根節點的索引值
    left_inorder = inorder[:root_idx]  # 中序走訪資料中左子樹資料
    right_inorder = inorder[root_idx+1:]  # 中序走訪資料中右子樹資料
    left_preorder = preorder[1:1+len(left_inorder)]  # 前序走訪資料中左子樹資料
    right_preorder = preorder[1+len(left_inorder):]  # 前序走訪資料中右子樹資料
    left_postorder = build_tree(left_preorder, left_inorder)  # 遞迴，找左子樹後序走訪資料
    right_postorder = build_tree(right_preorder, right_inorder)  # 遞迴，找右子樹後序走訪資料
    return left_postorder + right_postorder + root  # 組合成答案

result = []
lines = sys.stdin.readlines()
for line in lines:
    if not line.strip(): continue
    result.append(f"{build_tree(*line.split())}\n")
sys.stdout.write("".join(result))

用串列儲存二元樹走訪的資料，用時間約為 7 ms，記憶體約為 2.8 MB，通過測試。

import sys

def build_tree(preorder, inorder):
    if not preorder or not inorder: return []  # 如果沒有資料，回傳空串列
    root = preorder[0]  # 前序走訪開頭為根節點
    root_idx = inorder.find(root)  # 找到中序走訪資料中根節點的索引值
    left_inorder = inorder[:root_idx]  # 中序走訪資料中左子樹資料
    right_inorder = inorder[root_idx+1:]  # 中序走訪資料中右子樹資料
    left_preorder = preorder[1:1+len(left_inorder)]  # 前序走訪資料中左子樹資料
    right_preorder = preorder[1+len(left_inorder):]  # 前序走訪資料中右子樹資料
    left_postorder = build_tree(left_preorder, left_inorder)  # 遞迴，找左子樹後序走訪資料
    right_postorder = build_tree(right_preorder, right_inorder)  # 遞迴，找右子樹後序走訪資料
    return left_postorder + right_postorder + [root]  # 組合成答案

result = []
lines = sys.stdin.readlines()
for line in lines:
    if not line.strip(): continue
    ans = "".join(build_tree(*line.split()))
    result.append(f"{ans}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：c125. 00534 - Frogger

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


ZeroJudge 題目連結：c125. 00534 - Frogger

解題想法

先讀取所有石頭的位置，計算任意兩個石頭之間的距離，存入二維陣列 $dist$ 之中，其中 $dist[i][j]$ 代表石頭 $i, j$ 之間的距離。 開一個陣列 $ans$，儲存到達第 $i$ 個石頭的路徑上單次跳躍距離最大值之中的最小值。接下來用一個最小優先佇列 $pq$，資料為 $(距離, 石頭索引值)$，代表到第 $i$ 顆石頭的路徑上最大的單次跳躍距離，距離最小的資料放上面。如果 $pq$ 還有資料，而且 $pq$ 最上面的石頭索引值不等於 $1$（終點），while 迴圈繼續執行。每次取出 $pq$ 最上方的資料，目前的距離 $curr$、石頭索引值 $u$，掃過石頭 $v ~(0 \leq v \leq n-1)$，取 $curr$ 與 $dist[u][v]$ 較大者為新的距離 $new_{dis}$，如果 $new_{dis} < ans[v]$，更新 $ans[v]$，並將 ${new_{dis}, v}$ 加入 $pq$。

Python 程式碼

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

import sys, heapq

def cal_dis(a, b):  # 計算距離用的函式
    return ((a[0] - b[0])**2 + (a[1] - b[1])**2)**0.5

ca = 0
result = []
for line in sys.stdin:
    if not line.strip(): continue
    n = int(line)  # n 顆石頭
    if n == 0: break  # 中止迴圈的條件
    ca += 1
    if ca > 1: result.append("\n")  # 從第 2 筆測資開始要先空一行
    stones = [tuple(map(float, sys.stdin.readline().split())) for _ in range(n)]  # 石頭位置
    dist = [[0.0]*n for _ in range(n)]  # 石頭之間的距離
    for i in range(n):
        for j in range(n):
            if i == j: continue
            d = cal_dis(stones[i], stones[j])
            dist[i][j] = d
            dist[j][i] = d
    ans = [float('inf')]*n  # 到達第 i 個石頭的路徑上單次跳躍距離最大值之中的最小值
    pq = [(0.0, 0)]  #  (距離, 石頭索引值)，代表到第 $i$ 顆石頭的路徑上最大的單次跳躍距離
    while pq and pq[0][1] != 1:  # pq 還有資料，而且 pq 最上面的石頭索引值不等於 1
        curr, u = heapq.heappop(pq)  # 取出 pq 最上方的資料，目前的距離 curr、石頭索引值 u
        for v in range(n):  # 掃過石頭 v = 0 ~ n-1
            if v == u: continue  # 同一顆石頭，跳過
            new_dis = max(curr, dist[u][v])  # 新的距離
            if new_dis < ans[v]:  # 新的最小值
                ans[v] = new_dis  # 更新 ans[v]
                heapq.heappush(pq, (new_dis, v))  # (new_dis, v) 加入 pq
    result.append(f"Scenario #{ca:d}\nFrog Distance = {ans[1]:.3f}\n")
sys.stdout.write("".join(result))

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))