ZeroJudge 解題筆記：k205. 蝸牛的踩地雷攻略 1 (插旗)

作者：王一哲
日期：2025年11月27日


ZeroJudge 題目連結：k205. 蝸牛的踩地雷攻略 1 (插旗)

解題想法

我用二維陣列儲存地圖，並在周圍加上 _ 當作哨兵避免出界。依序掃過每個格子，如果這格不是數字，就跳過找下一格；如果是數字，計算周圍 8 格有幾個 # 或 P，並記錄這些位置，如果 # 及 P 的數量等於這格標記的數字，剛才記錄的位置都改成 P。

Python 程式碼

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

n, m = map(int, input().split())
grid = [list(input() + '_') for _ in range(n)]
grid.append(['_']*(m+1))
for r in range(n):
    for c in range(m):
        if not grid[r][c].isnumeric(): continue
        cnt = 0
        bomb = []
        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
            if grid[nr][nc] == '#' or grid[nr][nc] == 'P':
                cnt += 1
                bomb.append((nr, nc))
        if cnt == int(grid[r][c]):
            for nr, nc in bomb:
                grid[nr][nc] = 'P'
for row in grid[:n]:
    print("".join(row[:m]))

ZeroJudge 解題筆記：k076. 簡易棒球模擬

作者：王一哲
日期：2025年11月26日


ZeroJudge 題目連結：k076. 簡易棒球模擬

解題想法

這題跟〈c297. APCS-2016-1029-4棒球遊戲〉很像，按照題目的敘述處理壘上跑者、得分及出局數即可。

Python 程式碼

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

bases = list(map(int, input().split()))
hit = int(input())
runs = 0
if hit == 4:
    runs = 1 + sum(bases)
    bases = [0, 0, 0]
elif hit == 3:
    runs = sum(bases)
    bases = [1, 0, 0]
elif hit == 2:
    runs = sum(bases[:2])
    if bases[2] == 1:
        bases = [1, 1, 0]
    else:
        bases = [0, 1, 0]
elif hit == 1:
    if bases[0] == 1:
        runs = 1
        bases[0] = 0
    if bases[1] == 1:
        bases[0] = 1
        bases[1] = 0
    if bases[2] == 1:
        bases[1] = 1
    bases[2] = 1
print(runs)
print(*bases)

ZeroJudge 解題筆記：j568. 無預警小考 ( 上 )

作者：王一哲
日期：2025年11月25日


ZeroJudge 題目連結：j568. 無預警小考 ( 上 )

解題想法

按照題目要求的格式組合答案。我在 Python 先將所有要輸出的內容用字串格式儲存在串列之中，最後再接成很長的字串用 sys.stdout.write 輸出；在 C++ 則是每組合完一小段答案就用 cout 輸出。

Python 程式碼

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

import sys

t = int(sys.stdin.readline())
for _ in range(t):
    result = ["請使用配方法解下列一元二次方程式\n\n"]
    n = int(sys.stdin.readline())
    for i in range(1, n+1):
        cof = list(map(int, sys.stdin.readline().split()))
        eq = str(i) + ". "
        if cof[0] == 1: eq += "x^2"
        elif cof[0] == -1: eq += "-x^2"
        else: eq += str(cof[0]) + "x^2"
        if cof[1] == 0: pass
        elif cof[1] == 1: eq += "+x"
        elif cof[1] > 1: eq += "+" + str(cof[1]) + "x"
        elif cof[1] == -1: eq += "-x"
        else: eq += str(cof[1]) + "x"
        if cof[2] == 0: pass
        elif cof[2] > 0: eq += "+" + str(cof[2])
        else: eq += str(cof[2])
        eq += "=0\n\n"
        result.append(eq)
    result.append("考試要加油口屋\n\n")
    sys.stdout.write("".join(result))

ZeroJudge 解題筆記：a586. 4. 捷運計價問題

作者：王一哲
日期：2025年11月24日


ZeroJudge 題目連結：a586. 4. 捷運計價問題

解題想法

我用 BFS 解題，由於這題可以用不同的走法到達同一座車站，不能用是否已走訪這座車站來排除重複的走法。改用一個字典 prices 儲存由起點到達各車站的最低票價，如果經由現在的路線走到這座車站的票價大於目前已知的最低票價，代表這個走法走到終點時不可能是新的最低票價，不需要加入待走訪佇列 que 之中。由於 que 要儲存的資料為 (車站編號, 目前的票價, 經過站數, 轉乘路線數)，有 1 個字串及 3 個整數，在 C++ 我另外定義 struct Station 儲存資料。

Python 程式碼

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

from collections import defaultdict, deque

n = int(input())  # 接下來有 n 行
graph = defaultdict(list)  # 車站連接方式，無向圖
for _ in range(n):
    u, v = input().split()
    graph[u].append(v)
    graph[v].append(u)
start, end = input().split()  # 起點、終點
if start == end:  # 特例，起點、終點相同
    print(10)  # 最低票價 10 元
else:
    # 到各車站所需最低票價，預設為無窮大
    prices = defaultdict(lambda : float('inf'))
    prices[start] = 10  # 到起點票價 10 元
    # 待走訪佇列，資料為 (車站編號, 目前的票價, 經過站數, 轉乘路線數)
    que = deque([(start, 10, 0, 0)])
    while que:  # 用 BFS 找走到終點的最低票價
        curr, fee, cnt, trans = que.popleft()
        if curr == end:  # 走到終點
            prices[end] = min(prices[end], fee)  # 更新走到終點的最低票價
            continue  # 找下一個點，可能有其它更低票價的走法
        if fee > prices[end]:  # 目前票價大於已知到達終點的最低票價
            continue  # 找下一個點，不可能是新的最低票價
        for nxt in graph[curr]:  # 依序讀取相連的車站
            new_cnt = cnt + 1  # 經過站數加 1
            if nxt[0] != curr[0]: new_trans = trans + 1  # 轉乘不同路線
            else: new_trans = trans
            new_fee = 10 + new_cnt//3*5 + new_trans*5  # 新的票價
            if new_fee > prices[nxt]:  # 到達此站的票價超過已知的最低票價
                continue  # 找下一個點，不可能是新的最低票價
            prices[nxt] = new_fee
            que.append((nxt, new_fee, new_cnt, new_trans))
    print(prices[end])

ZeroJudge 解題筆記：i646. 排列組合-排列

作者：王一哲
日期：2025年11月23日


ZeroJudge 題目連結：i646. 排列組合-排列

解題想法

這題原來應該是要考用函式遞迴及回溯，但是在 Python 可以用 itertools.permutatinos 産生所有的排列，在 C++ 可以用 algorithm 函式庫的 next_permutation。

Python 程式碼

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

import sys

def perm(n, s):
    if len(s) == n:
        print(s)
        return 
    for i in range(n):
        c = chr(i + ord('a'))
        if c in s: continue
        perm(n, s+c)

for line in sys.stdin:
    n = int(line)
    if n == 0: break
    perm(n, "")

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

import sys
from itertools import permutations

result = []
lines = sys.stdin.readlines()
for line in lines:
    n = int(line)
    if n == 0: break
    chars = [chr(i + ord('a')) for i in range(n)]
    for perm in permutations(chars):
        s = "".join(perm)
        result.append(f"{s}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：i706. B.永遠ㄉ神（yyds）

作者：王一哲
日期：2025年11月22日


ZeroJudge 題目連結：i706. B.永遠ㄉ神（yyds）

解題想法

用堆疊 st 記錄前方的人身高及索引值，堆疊中先放入 (-float('inf'), 0) 避免遇到空堆疊的狀況。每次讀取第 i 個人的身高 h，用 while 迴圈從 st 最上方開始檢查，移除所有身高大於 h 的資料，當 while 迴圈結束之後，st 最上方的資料的索引值就是要輸出的答案，再將 (h, i) 加入 st。

Python 程式碼

使用時間約為 0.4 s，記憶體約為 165.3 MB，通過測試。

import sys

n = int(sys.stdin.readline())
st = [(-float('inf'), 0)]
ans = []
for i, h in enumerate(map(int, sys.stdin.readline().split()), start=1):
    while st[-1][0] >= h: st.pop()
    ans.append(str(st[-1][1]))
    st.append((h, i))
sys.stdout.write(" ".join(ans) + "\n")

ZeroJudge 解題筆記：a584. 2. 親等關係

作者：王一哲
日期：2025年11月21日


ZeroJudge 題目連結：a584. 2. 親等關係

解題想法

題目看起來像是樹，但其實用字典及串列儲存無向圖，再用 BFS 找兩個人之間的距離就過關了。如果用 Python 解題可以用 collections.defaultdict 存圖，這樣可以不需要檢查 key 值是否已在字典之中。我用 Python 寫這題很順利，反而是用 C++ 解題是吃了好幾次 WA，後來發現測資在第 1 行的人數 n 之後換行的格式可能比較特別，我一開始只有 cin.ignore() 跳過一個 \n，但是這樣會吃 WA，改成用 getline 讀取一整行才過關。

Python 程式碼

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

from collections import defaultdict, deque

""" 讀取測資並存圖 """
n = int(input())  # n 個人
graph = defaultdict(list)  # 無向圖，用字串當作 key，list 裡面存字串
for _ in range(n):  # 讀取 n 行
    names = input().split()  # 名字，用空格分割
    parent = names[0]  # 父節點名稱
    children = names[1:]  # 子節點名稱，可能有多個子節點
    for child in children:  # 依序讀取每個子節點名稱
        graph[parent].append(child)  # 儲存節點之間連接的方式
        graph[child].append(parent)
""" 讀取最後一行並用 BFS 找答案 """
a, b = input().split()  # 要找距離的兩個人名
que = deque([(a, 0)])  # 待走訪佇列，資料為 (節點, 距離)，先存入 (a, 0)
ans = 0  # 答案
visited = {a}  # 用 set 儲存已走訪節點名稱
while que:  # 如果 que 有資料繼續執行
    u, d = que.popleft()  # 從 que 開頭取出節點 u、距離 d
    if u == b:  # 如果 u 等於 b，找到終點
        ans = d  # 答案為 d
        break  # 中止迴圈
    for v in graph[u]:  # 依序讀取與 u 相連的節點 v
       if v in visited: continue  # 如果 v 已走訪過，找下一個節點
       visited.add(v)  # v 加入 visited
       que.append((v, d+1))  # (v, d+1) 加入 que
# 結束 BFS，印出答案
print(ans)

ZeroJudge 解題筆記：i645. 排列組合-組合

作者：王一哲
日期：2025年11月20日


ZeroJudge 題目連結：i645. 排列組合-組合

解題想法

這題原來應該是要考用函式遞迴及回溯，但是在 Python 可以用 itertools.combinations 産生所有的組合。

Python 程式碼

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

import sys

def comb(n, m, start, s):
    if len(s) == m:
        print(s)
        return 
    for i in range(start, n):
        c = chr(i + ord('a'))
        comb(n, m, i+1, s+c)

for line in sys.stdin:
    n, m = map(int, line.split())
    if n == 0 and m == 0: break
    comb(n, m, 0, "")

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

import sys
from itertools import combinations

result = []
for line in sys.stdin:
    n, m = map(int, line.split())
    if n == 0 and m == 0: break
    chars = [chr(i + ord('a')) for i in range(n)]
    for comb in combinations(chars, m):
        s = "".join(comb)
        result.append(f"{s}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：i644. 列舉八皇后問題所有解

作者：王一哲
日期：2025年11月19日


ZeroJudge 題目連結：i644. 列舉八皇后問題所有解

解題想法

經典的題目，用函式遞迴及回溯比較好寫。

Python 程式碼

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

def solve_n_queens(n):  # 自訂函式，解 n 皇后問題
    # 回溯，代入目前的列，已用的欄、左上右下斜線、右上左下斜線
    def backtrack(row, cols, diag1, diag2):
        if row == n:  # 遞迴出口，填入第 n 列，找到一組解
            # 將 borad 儲存的欄與列組成 tuple，依照欄排序，存入 ans
            # 由 ans 取出列的順序，轉成字串，存入 solutions
            ans = sorted([(c, i) for i, c in enumerate(board, start=1)])
            solutions.append("".join([str(i) for _, i in ans]))
        for col in range(n):  # 依序測試第 0 ~ n-1 欄
            d1 = row - col  # 左上右下斜線
            d2 = row + col  # 右上左下斜線
            # 如果 col, d1, d2 不在已用的集合之中，可以用這個位置
            if col not in cols and d1 not in diag1 and d2 not in diag2:
                board[row] = col  # row 列使用的欄為 col
                # 遞迴，找下一列，代入原來的集合分別與 col, d1, d2 的聯集
                backtrack(row+1, cols | {col}, diag1 | {d1}, diag2 | {d2})
    # end of backtrack
    solutions = []  # 所有的解
    board = [-1]*n  # 第 row 列的皇后放在第 col 欄
    backtrack(0, set(), set(), set())  # 呼叫 backtrack 求解
    return solutions  # 回傳所有的解
# end of solve_n_queens
all_solutions = solve_n_queens(8)
all_solutions.sort()  # 依照字典排序
for i, sol in enumerate(all_solutions, start=1):
    print(f"{i:d}: {sol:s}")

ZeroJudge 解題筆記：i510. 尋找子字串

作者：王一哲
日期：2025年11月18日


ZeroJudge 題目連結：i510. 尋找子字串

解題想法

這題用字串的 find 功能很好寫。

Python 程式碼

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

import sys

for line in sys.stdin:
    n, m = map(int, line.split())
    s, t = sys.stdin.readline().split()
    idx = s.find(t)
    if idx == -1: print("No")
    else: print(f"Yes\npos: {idx:d}")