LeetCode 解題筆記：3364. Minimum Positive Sum Subarray

作者：王一哲
日期：2026年11月14日


LeetCode 題目連結：3364. Minimum Positive Sum Subarray

解題想法

簡單題。題目給一個長度為 $n$ 的整數陣列 $nums$，兩個整數 $l, r$，要找出大於 0 的子陣列加總的最小值，子陣列長度 $length ~(l \leq length \leq r)$。我先計算 $nums$ 的前綴和 $psum$，再用雙層 for 迴圈測試所有可能的右端點 $i$ 及子陣列長度 $d$ 找答案，時間複雜度為 $O(n^2)$，因為這題的 $n$ 不大，速度很快。

Python 程式碼

Runtime: 9 ms, beats 97.54%. Memory: 19.16 MB, beats 87.19%.

class Solution:
    def minimumSumSubarray(self, nums: List[int], l: int, r: int) -> int:
        n = len(nums)
        
        # 1. 計算 nums 的前綴和
        psum = [0] + nums[:]
        for i in range(1, n+1):
            psum[i] += psum[i-1]
        
        # 2. 用雙層 for 迴圈測試所有可能的右端點及子陣列長度找答案
        ans = float('inf')
        for i in range(l, n+1):
            for d in range(l, min(i, r) + 1):
                isum = psum[i] - psum[i-d]
                if isum > 0 and isum < ans:
                    ans = isum
        return ans if ans < float('inf') else -1

ZeroJudge 解題筆記：c231.踩地雷

作者：王一哲
日期：2026年11月14日


ZeroJudge 題目連結：c231.踩地雷

解題想法

每組測資第一列為 3 個整數 $a, b, n$，$a, b$ 代表地圖大小為 $a \times b$，$n$ 代表有地雷數量。接下來 $n$ 列每列有 2 個整數 $row_i, col_i ~(1 \leq row_i, col_i \leq 10^4)$，代表第 $i$ 個地雷的位置。每個地雷周圍 8 格有感測器，如果某一個地雷爆炸時，周圍 8 格之中有其它地雷的感測器，則這些地雷會跟著被引爆。如果要用誘導彈引爆所有的地雷，至少需要幾個誘導彈？

這題我用 BFS 處理。先將地雷的坐標存入串列 $mines$，將感測器坐標對應的地雷編號存入字典 $sensors$，key 值為 tuple 格式的坐標 $(r, c)$，value 為串列格式。另外用一個 set 或陣列 $rem$ 記錄目前未被引爆的地雷編號。用一個 for 迴圈依序讀取地雷編號，如果遇到還沒有被引爆的地雷，答案 $ans + 1$，將這個地雷編號加入待走訪佇列 $que$，用 BFS 跑完所有會連鎖反應的地雷。這個寫法有點慢，但是比較容易理解。

Python 程式碼

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

def solve():
    import sys
    from collections import deque

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        a = int(data[ptr])  # 地圖 a 列
        b = int(data[ptr + 1])  # b 欄
        n = int(data[ptr + 2])  # n 個地雷
        ptr += 3

        mines = []  # 地雷坐標
        sensors = dict()  # 感測器坐標對應的地雷編號 (r, c): idx
        dr = (0, 1, 1, 1, 0, -1, -1, -1)  # 周圍 8 格的位移量
        dc = (1, 1, 0, -1, -1, -1, 0, 1)  # 周圍 8 格的位移量
        for i in range(n):
            r = int(data[ptr])
            c = int(data[ptr + 1])
            ptr += 2
            mines.append((r, c))
            for j in range(8):
                nr, nc = r + dr[j], c + dc[j]
                if (nr, nc) not in sensors:
                    sensors[nr, nc] = [i]
                else:
                    sensors[nr, nc].append(i)
        
        ans = 0  # 答案
        rem = set(range(n))  # 剩下的地雷
        for i in range(n):
            if i in rem:
                rem.remove(i)
                ans += 1
                # 測試周圍 8 格是否有其它未爆地雷的感測器
                que = deque([i])
                while que:
                    r, c = mines[que.popleft()]
                    for j in range(8):
                        nr, nc = r + dr[j], c + dc[j]
                        for k in sensors[nr, nc]:
                            if k in rem:
                                rem.remove(k)
                                que.append(k)
        result.append(f"{ans:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：c230.松鼠旅行

作者：王一哲
日期：2026年11月13日


ZeroJudge 題目連結：c230.松鼠旅行

解題想法

每組測資第一列為一個整數 $N ~(1 \leq N \leq 10^5)$，代表有 $N$ 棵樹。接下來 $N$ 列，每列有 3 個整數 $x_i, y_i ~(1 \leq x_i, y_i \leq 10^4)$、$h ~(1 \leq h_i \leq 10^5)$，代表第 $i$ 棵樹的位置為 $(x_i, y_i)$、高度為 $h_i$。起點為 $(0, 0)$，終點為 $(10000, 10000)$，這 $N$ 棵樹之中必定有兩棵樹位於起點和終點。路徑上選擇的樹只能離起點越來越遠。找出在路徑上任意兩棵樹最大的下降高度，除了起點、終點之外，其它的樹不一定需要經過。

先讀取 $N$ 棵樹的位置、高度，存入陣列 $trees$，再依照 $x^2 + y^2$ 由小到大排序。定義最大高度 $hmax = trees[0].h$、答案 $ans = 0$。用一個 for 迴圈掃過第 $i$ 到第 $n-1$ 棵樹，先更新 $hmax = max(hmax, trees[i].h)$，再更新 $ans = max(ans, hmax - trees[i].h)$。跑完 for 迴圈之後印出 $ans$。

Python 程式碼

這題的記憶體上限很小，只有 16 MB，用 Python 無法過關，會遇到以下的錯誤訊息。

您的程式被監控系統中斷，可能是程式無法正常結束所導致。
Fatal Python error: init_import_site: Failed to import the site module
Python runtime state: initialized
Traceback (most recent call last):
  File "<frozen importlib._bootstrap>", line 1360, in _find_and_load
MemoryError
Exited with error status 1

while True:
    try:
        n = int(input())
    except EOFError:
        break

    trees = [tuple(map(int, input().split())) for _ in range(n)]
    trees.sort(key = lambda x : x[0]**2 + x[1]**2)
    hmax, ans = trees[0][2], 0
    for i in range(1, n):
        hmax = max(hmax, trees[i][2])
        ans = max(ans, hmax - tree[i][2])

    print(ans)

ZeroJudge 解題筆記：o874.搶地棋 (Chess)

作者：王一哲
日期：2026年11月12日


ZeroJudge 題目連結：o874.搶地棋 (Chess)

題目 pdf 檔連結：搶地棋 (Chess)

解題想法

每組測資第一列為兩個整數 $R, C ~(3 \leq R, C \leq 7)$，代表棋盤的尺寸為 $R \times C$。接下來 $R$ 列、每列有一個長度為 $C$ 的字串，字串中只包含代表棋子的 @ 及代表空地的 #。最多只會有 25 個棋子。玩家 Charlie 先手，Dave 後手。每次行動時要從棋盤上移除符合騎士步的兩個棋子，如果無法移除這樣的棋子則輸掉比賽。由初始盤面狀態預設贏家。

這題考狀態壓縮，因為最多只有 25 個棋子，可以用一個最大為 $2^{25} - 1 = 33554431$ 的整數 $mask$ 代表編號為 $0$ 到 $24$ 的棋子是否在盤面上，如果 $mask$ 第 $i$ 位數為 $1$，代表編號 $i$ 的棋子在盤面上。將各個棋子的坐標存入陣列 $piece$ 之中。用兩層 for 迴圈跑出所有符合騎士步的棋子組合，存入陣列 $masks$ 之中。

這題考的第二個技巧是記憶化 DFS，呼叫自訂函式 dfs 時代入初始盤面狀態 $init$，找出 $init$ 對應的勝負關係。用一個字典或是二維陣列 $memo$ 記錄各種盤面狀態對應的勝負關係。如果用字典記錄狀態，以盤面狀態 $init$ 作為 key 值，如果 $init$ 不在 $memo$ 之中，代表還沒有計算過 $init$ 對應的勝負關係，需要往下遞迴；反之，回傳 $memo[init]$，True 代表目前的玩家必勝，Fasle 代表目前的玩家必敗。遞迴前要先找出下一個狀態 $nxt$，從 $masks$ 之中讀取各種符合騎士步的狀態 $mask$，如果要被移除的兩個棋子在 $init$ 之中，用 XOR 計算出下一個狀態 $nxt$。遞迴，呼叫 $dfs(nxt)$，如果回傳 Fasle，代表下一個行動的玩家必敗，目前的玩家必勝，回傳 True。如果測試完所有的 $mask$ 之後沒有任何遞迴結果為 False，代表目前的玩家必敗，回傳 False。

如果改用二維陣列記錄各種盤面狀態對應的勝負關係，則用 $-1$ 代表還沒有計算過的狀態，$0$ 代表對應的玩家必敗，$1$ 代表目前的玩家必勝。

Python 程式碼

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

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        # 1. 讀取棋盤及棋子的位置
        R = int(data[ptr])
        C = int(data[ptr + 1])
        ptr += 2

        piece = []  # 棋子的位置
        for i in range(R):
            row = data[ptr]
            ptr += 1
            for j, c in enumerate(row):
                if c == '@':
                    piece.append((i, j))
        
        # 2. 計算所有符合騎士步規則的狀態
        N = len(piece)  # 騎子的數量
        masks = []
        for i in range(N):
            for j in range(i+1, N):
                dr = abs(piece[i][0] - piece[j][0])
                dc = abs(piece[i][1] - piece[j][1])
                if (dr == 2 and dc == 1) or (dr == 1 and dc == 2):
                    masks.append((1 << i) | (1 << j))

        # 3. 記憶化 DFS，找出初始狀態 init 對應的勝負關係
        memo = [-1] * (1 << N)  # -1 沒有，0 敗，1 勝
        
        def dfs(init):
            # 遞迴出口，memo 之中有 init 對應的結果，直接回傳 
            if memo[init] != -1:
                return memo[init]
            
            # 測試所有可能的狀態
            for mask in masks:
                # 如果 init 之中有 mask 要移除的棋子
                if (init & mask) == mask:
                    # 用 XOR 計算新的狀態 nxt
                    nxt = init ^ mask
                    # 遞迴，如果 nxt 使對手必敗，則自己必勝，回傳 1
                    if dfs(nxt) == 0:
                        memo[init] = 1
                        return 1
            
            # 測試完畢，沒有觸發第 46 行，自己必敗
            memo[init] = 0
            return 0
        
        # 4. 呼叫 dfs，代入所有棋子都在盤面上的狀態求解
        full_mask = (1 << N) - 1
        result.append("Charlie\n" if dfs(full_mask) else "Dave\n")

    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：3105. Longest Strictly Increasing or Strictly Decreasing Subarray

作者：王一哲
日期：2026年11月12日


LeetCode 題目連結：3105. Longest Strictly Increasing or Strictly Decreasing Subarray

解題想法

簡單題。題目給一個長度為 $n$ 的整數陣列 $nums$，要找出嚴格遞增或嚴格遞減的子陣列最大長度。用 3 個變數 $ans, inc, dec$ 記錄答案、最長嚴格遞增長度、最長嚴格遞減長度，如果只取 $nums[0]$，則 3 者皆為 1。再用一個 for 迴圈，測試 $i = 1$ 到 $i = n-1$，如果 $nums[i] > nums[i-1]$，嚴格遞增，$inc + 1$，$dec = 1$；如果 $nums[i] < nums[i-1]$，嚴格遞減，$dec = 1$，$inc = 1$；如果 $nums[i] = nums[i-1]$，$inc = 1$，$dec = 1$；再更新 $ans$。

Python 程式碼

Runtime: 1 ms, beats 58.21%. Memory: 19.21 MB, beats 53.17%.

class Solution:
    def longestMonotonicSubarray(self, nums: List[int]) -> int:
        n = len(nums)  # 長度
        ans = inc = dec = 1  # 答案、遞增、遞減長度，如果只取 nums[0]，長度為 1

        for i in range(1, n):  # 測試 i = 1 ~ n-1
            if nums[i] > nums[i-1]:  # 遞增，inc 加 1，dec 變成 1
                inc += 1
                dec = 1
            elif nums[i] < nums[i-1]:  # 遞減，dec 加 1，inc 變成 1
                dec += 1
                inc = 1
            else:  # 相等，ind、dec 皆變為 1
                inc = dec = 1
            ans = max(ans, inc, dec)  # 更新 ans
        
        return ans

LeetCode 解題筆記：3789. Minimum Cost to Acquire Required Items

作者：王一哲
日期：2026年11月11日


LeetCode 題目連結：3789. Minimum Cost to Acquire Required Items

解題想法

中等難度題。題目給 5 個整數，$cost1$ 代表單獨買 1 單位的物品 1 的價格，$cost2$ 代表單獨買 1 單位的物品 2 的價格，$costBoth$ 代表同時買 1 單位的物品 1 及 1 單位的物品 2 的價格，$need1$ 代表物品 1 需要買的數量，$need2$ 代表物品 2 需要買的數量，求買到需要的數量至少需要花多少錢？

這題考數學。先試著一起買 $need1, need2$ 之中最少的數量，假設量值為 $buyBoth$，選擇一起買 $costBoth$ 或分開買 $cost1 + cost2$ 之中比較省錢的方案，將金額加到答案 $ans$，再更新 $need1, need2$，減去已經購買的量 $buyBoth$。接下來買需求 1 剩下的量，如果 $need1 > 0$ 才需要計算，$ans$ 再加上 $costBoth, cost1$ 較低者乘以 $need1$，由於題目只要求最低花費，不需要計算多買的量，不用再更新 $need1$。最後買需求 2 剩下的量，如果 $need2 > 0$ 才需要計算，$ans$ 再加上 $costBoth, cost2$ 較低者乘以 $need2$。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.22 MB, beats 71.58%.

class Solution:
    def minimumCost(self, cost1: int, cost2: int, costBoth: int, need1: int, need2: int) -> int:
        # 先試著一起買，選擇一起買或分開買之中比較省錢的方案
        buyBoth = min(need1, need2)  # 需求 1、2 較小的數字
        ans = min(costBoth, cost1 + cost2) * buyBoth
        # 更新需求量
        need1 -= buyBoth
        need2 -= buyBoth
        
        # 買需求 1 剩下的量
        if need1 > 0:
            ans += min(costBoth, cost1) * need1
        
        # 買需求 2 剩下的量
        if need2 > 0:
            ans += min(costBoth, cost2) * need2
        
        return ans

ZeroJudge 解題筆記：f174.m6a2-蛋糕(Cake)

作者：王一哲
日期：2026年11月11日


ZeroJudge 題目連結：f174.m6a2-蛋糕(Cake)

解題想法

每組測資第一列為兩個整數 $N ~(1 \leq N \leq 10^5)$ 及 $K ~(1 \leq K \leq N)$，代表共有 $N$ 塊蛋糕，最多可以吃連續 $K$ 塊蛋糕。第二列為 $N$ 個整數，分別代表每一塊蛋糕的分數。要找出可以吃到的最高總分。

這題考前綴和及滑動視窗。先讀取每塊蛋糕的分數存入陣列 $psum$，開頭多存一個 0，再轉成前綴和，之前用來計算連續區間和。用雙向佇列 $dq$ 儲存滑動視窗區間索引值，出界的索引值從前端移除，後端加入較小的前綴和索引值，前綴和最小的索引值在 $dq$ 前端。$dq$ 先放入 0，最高分數 $imax = 0$。用一個 for 迴圈測試右端點 $i = 1$ 到 $i = n$，目前的區間為 $i-k+1$ 到 $i$，$dq$ 左端為區間左端前一格 $i-k$。用 while 迴圈移除左端已出界的索引值。如果移除後 $dq$ 有資料，$psum[i] - psum[dq[0]]$ 可能是新的最大值，更新 $imax$。再用一個 while 迴圈，移除 $dq$ 右端大於、等於 $psum[i]$ 的索引值，移除後 $i$ 加入 $dq$ 右端。

Python 程式碼

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

def solve():
    import sys
    from collections import deque

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])  # n 塊蛋糕
        k = int(data[ptr + 1])  # 最多吃連續 k 塊蛋糕
        ptr += 2

        # 讀取 n 塊蛋糕的分數，再轉成前綴和
        psum = [0] + list(map(int, data[ptr : ptr + n]))
        ptr += n
        for i in range(1, n+1):
            psum[i] += psum[i-1]
        
        # 用 dq 儲存滑動視窗區間索引值，出界的索引值從前端移除，
        # 後端加入較小的前綴和索引值，前綴和最小的索引值在 dq 前端
        dq = deque([0])  # 先放入 0
        imax = 0  # 最大區間和
        for i in range(1, n+1):  # 測試右端 i = 1 ~ n
            # 區間為 [i-k+1 : i+1]，dq 左端為前一格 i-k，不包含 i+1，移除左端已出界的索引值
            while dq and i - dq[0] > k:
                dq.popleft()
            
            # 計算目前的區間和並更新最高分
            if dq:
                imax = max(imax, psum[i] - psum[dq[0]])

            # 移除 dq 右端大於、等於 psum[i] 的索引值
            while dq and psum[dq[-1]] >= psum[i]:
                dq.pop()

            # i 加入 dq 右端
            dq.append(i)
        
        # 印出結果
        result.append(f"{imax:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：3693. Climbing Stairs II

作者：王一哲
日期：2026年11月10日


LeetCode 題目連結：3693. Climbing Stairs II

解題想法

中等難度題。題目給一個整數 $n ~(1 \leq n \leq 10^5)$，代表有 $n$ 階樓梯，再給一個從 1 開始編號的陣列 $costs$，$costs[i] ~(1 \leq costs[i] \leq 10^4)$ 代表走到第 $i$ 階樓梯需要的成本。每次可以走 1、2 或 3 階樓梯，如果從第 $i$ 階往上走到第 $j$ 階，總成本分為 $cost[j] + (j - i)^2$，計算走到第 $n$ 階的最低成本。

這題考動態規畫。假設要走到第 $i$ 階，3 個變數 $d1, d2, d3$ 分別代表從第 $i-1, i-2, i-3$ 階走上來的最低累計成本，初始值分別為 $0, inf, inf$。接下來用 for 迴圈跑 $i = 1$ 到 $i = n$，走到第 $i$ 階的最低成本為 $curr = cost[i - 1] + min(d1 + 1, d2 + 4, d3 + 9)$，再更新狀態，$curr$ 給 $d1$，$d1$ 給 $d2$，$d2$ 給 $d3$。跑完 for 迴圈之後，答案在 d1。

Python 程式碼

Runtime: 175 ms, beats 92.45%. Memory: 33.42 MB, beats 50.28%.

class Solution:
    def climbStairs(self, n: int, costs: List[int]) -> int:
        # 假設走到第 i 階，d1、d2、d3 分別代表從 i-1、i-2、i-3 走到 i 的最低累計成本
        d1, d2, d3 = 0, float('inf'), float('inf')
        
        # 從第 1 格走到第 n 格
        for i in range(1, n + 1):
            # 取從 d1 走 1 格、d2 走 2 格、d3 走 3 格的最低成本
            curr = costs[i - 1] + min(d1 + 1, d2 + 4, d3 + 9)
            # 更新狀態，curr 給 d1，d1 給 d2, d2 給 d3
            d1, d2, d3 = curr, d1, d2
        # 最後答案在 d1
        return d1

ZeroJudge 解題筆記：f171.m5a2-快樂數字(HappyNumber)

作者：王一哲
日期：2026年11月10日


ZeroJudge 題目連結：f171.m5a2-快樂數字(HappyNumber)

解題想法

題目將快樂數字定義為符合以下 3 個條件的數字：

1. 不包含 0
2. 包含數字 1 ~ 9
3. 相鄰的數字最多相差 2

每組測資第一列為整數 $N ~(1 \leq N \leq 10^4)$，代表接下來有 $N$ 次詢問。接下來 $N$ 列每列有兩個整數 $P ~(1 \leq P \leq 10^3)$、$Q ~(1 \leq Q \leq 9)$，代表 $P$ 位數、最後一位數字為 $Q$ 的快樂數字，回傳對應的快樂數字數量並對 $10^9 + 7$ 取餘數。

這題考狀態壓縮及動態規畫。因為數字只有 $1$ ~ $9$，可以用一個整數 $mask ~(1 \leq mask \leq 511)$ 代表數字 $1$ 到 $9$ 的狀態，如果這個 $mask$ 轉成 2 進位制之後第 $i$ 位為 $1$，代表數字 $i+1$ 有出現。由於查詢的筆數很多，可以先建表，開一個 $1001 \times 10$ 的二維陣列 $ans$，$ans[i][j]$ 代表 $i$ 位數、結尾為 $j$ 的快樂數字數量。

用動態規畫填表。定義一個 $9 \times 512$ 的二維陣列 $dp$ 記錄數字數量，$dp[j][mask]$ 代表最後一位為 $j$、狀態為 $mask$ 的數量。先初始化 1 位數的狀況，用一個 for 迴圈跑 $j = 1$ 到 $j = 9$，$dp[j][1 << (j - 1)] = 1$。再用一個 for 迴圈跑 2 到 1000 位數的狀況，每次先開一個 $9 \times 512$ 的二維陣列 $nxt$ 記錄新的狀態，裡面再用 3 層 for 迴圈，由外到內分別跑這個數字可能的結尾 $j = 1$ 到 $j = 9$，前一個數字可能的結尾 $k = 1$ 到 $k = 9$，如果 $|j - k| \leq 2$ 再跑所有可能的 $mask$ 更新 $nxt$，跑完這 3 層之後再將 $nxt$ 存到 $dp$。將這次得到的 $i$ 位數、各種尾數 $j$ 對應的快樂數字數量加到 $ans[i][j]$，快樂數字數量在 $dp[1][511]$ 到 $dp[9][511]$ 之中。

Python 程式碼

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

def solve():
    import sys
    
    mod = 1000000007  # 取餘數用的質數

    # ans[i][j] 代表 i 位數、結尾為 j 的快樂數字數量
    ans = [[0] * 10 for _ in range(1001)]

    # 預計算 P = 1 ~ 1000 所有的答案
    def precompute():
        # dp[j][mask] 代表結尾為 j，數字 1 ~ 9 出現狀態的 mask 的方法數
        # mask 最大為 0b111111111 = 511
        dp = [[0] * 512 for _ in range(10)]
        
        # 初始化，長度 1，只有 1 個數字 j
        for j in range(1, 10):
            dp[j][1 << (j-1)] = 1
        
        # 更新 P = 2 ~ 1000
        for i in range(2, 1001):
            nxt = [[0] * 512 for _ in range(10)]  # 新的狀態
            
            for j in range(1, 10):  # 可能的結尾 j = 1 ~ 9
                for k in range(1, 10):  # 前一個長度的結尾 k = 1 ~ 9 
                    if abs(j - k) <= 2:  # 相鄰的數字最多差 2
                        for mask in range(512):  # 前一個位數的 mask
                            if dp[k][mask] > 0:  # 有對應的方法數
                                new_mask = mask | (1 << (j-1))  # 加入 j 之後的 mask
                                nxt[j][new_mask] = (nxt[j][new_mask] + dp[k][mask]) % mod
            # 更新 dp 為 nxt，跑下一個長度
            dp = nxt

            # 更新 ans[i][j] 為 dp[j][511]，mask = 511 = 0b111111111 代表有 1 ~ 9 所有的數字
            for j in range(1, 10):
                ans[i][j] = dp[j][511]
    # End of precompute，呼叫 precompute 計算答案
    precompute()
    
    # 讀取測資後查表找答案
    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])  # n 次詢問
        ptr += 1
        for _ in range(n):
            p = int(data[ptr])
            q = int(data[ptr + 1])
            ptr += 2
            result.append(f"{ans[p][q]:d}\n")
    
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：c520.5. 寶島老闆

作者：王一哲
日期：2026年11月9日


ZeroJudge 題目連結：c520.5. 寶島老闆

解題想法

測資第一列為兩個整數 $H, W$，代表地圖的尺寸為 $H \times W$。接下來 $H$ 列，每列為長度 $W$ 的字串，字串中只有代表空地的 . 及代表障礙物的 #。下一列為整數 $N$，代表接下來有 $N$ 天，每天設立一座工廠。最後有 $N$ 列，每列兩個整數 $a, b$，代表這一天工廠設立在坐標 $(a, b)$，坐標由 1 開始編號。工廠發出的汙染物每天會向右、下、左、上的空地擴散一格，輸出每一天結束時被汙染格子的數量。

這類向四周擴散的題目很適合用 BFS 解題，不過這題的陷阱很多，例如工廠設立的位置可能已經被汙染，已經有汙染物從這格向四周擴散，不需要加上這座工廠。可能設在相同的位置重複設立工廠，這也是無效的操作。障礙物可能包圍某一塊區域，汙染物被完全擋位。不過最麻煩的一點在於需要輸出每一天結束時被汙染格子數量，在 BFS 的過程需要很小心。待走訪佇列 $que$ 之中加入目前被汙染的格子坐標。用一個 for 迴圈跑 $n$ 天，先計算當時 $que$ 的長度 $m$，跑完 $que$ 前 $m$ 項時，代表已經檢查完在這一天之中會擴散的格子，這時再加試著加入新設立的工廠坐標，如果這格已經被汙染就不需要加入 $que$，如果有加入 $que$ 則答案 $ans$ 要跟著加 1。

Python 程式碼

程式碼的邏輯是對的，但是速度太慢，只能通過 58% 的測資。

def solve():
    import sys
    from collections import deque
    
    def get_tokens():
        for line in sys.stdin:
            for part in line.split():
                yield part

    tokens = get_tokens()
    result = []

    while True:
        try:
            h = int(next(tokens))
        except StopIteration:
            break
        
        # 地圖尺寸 h*w，轉成二維 list 才能修改字元
        w = int(next(tokens))
        grid = [list(next(tokens)) for _ in range(h)]
        
        # 讀取 n 間工廠的位置，並改成 0-index
        n = int(next(tokens))
        factory = [(int(next(tokens)) - 1, int(next(tokens)) - 1) for _ in range(n)]
        
        # 以天為單位 BFS 找答案
        ans = 0
        que = deque()

        for day in range(n):
            # 1. 處理第 day 天的汙染物擴散狀況，第 0 天會跳過這一段
            sz = len(que)
            for _ in range(sz):
                pos = que.popleft()
                r, c = pos // w, pos % w
                for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < h and 0 <= nc < w and grid[nr][nc] == '.':
                        ans += 1
                        grid[nr][nc] = '@'  # 被汙染的格子標記成 @
                        que.append(nr * w + nc)

            # 2. 試著加入新的工廠，如果這個位置沒被汙染才加入 que 並將 ans 加 1
            y, x = factory[day]
            if grid[y][x] == '.':
                grid[y][x] = '@'  # 被汙染的格子標記成 @
                que.append(y * w + x)
                ans += 1

            # 3. 印出第 day 天結束時的答案
            result.append(f"{ans:d}\n")

    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()