994. Rotting Oranges

──────────────────────────────────────────────────────────────────────

網格裡有空格（0）、新鮮橘子（1）、爛橘子（2）。每分鐘，爛橘子會把上下左右相鄰的新鮮橘子傳染成爛的。問最少幾分鐘所有橘子都會爛掉；如果有橘子永遠不會爛，回傳 -1。

思路

題目有說明的有，腐爛的橘子會影響旁邊的好橘子，好橘子會爛掉；如果好橘子相連的好橘子有和爛橘子相連，過了一段時間後也會爛掉；如果有橘子沒有和任何的爛橘子相鄰就不會壞掉。

先確定邊界

除了題目有說明的點以外，還有幾個條件要先確定好：

如果所有橘子都是壞掉的，那要回傳的時間為零
如果一個橘子都沒有，回傳的時間為零
如果所有橘子都是好的，回傳的時間為 -1

這三條在動手前先講出來，面試官會知道你有在想邊界，而且第 3 條和第 1 條長得很像卻答案完全相反，是最容易漏的。

為什麼一定要多源

這個題目的技巧在於，一開始要把所有的爛掉的橘子放在出發點，並且透過 BFS 同時出發；當全部的橘子都探索完了，就可以知道要花多少時間了，所需要花的時間就是 BFS 所走的層數。

「一顆一顆爛橘子各跑一次 BFS」不只是慢，而是做法不對：每顆新鮮橘子的腐爛時間取決於離它最近的那顆爛橘子，所以單源跑完之後還要對每一格取 min，才能得到正確答案 —— 那是 $O (k \cdot m n)$ 而且要多開一個距離陣列。

多源 BFS 直接繞過這件事：所有爛橘子都在第 0 層，波前齊步往外推，任何一格第一次被碰到就是最短時間，不需要比較。

怎麼知道還有沒有新鮮橘子

這裡有另外一個點是，要如何知道有沒有橘子壞掉？第一個直覺的方法是全部感染完後，重新掃描看看還有沒有好的橘子就好了。其實這樣做不會造成太多的理論時間複雜度的差別，但是這樣會讓 code 變得很複雜。

第二個方法是我們一開始的時候就計算出有多少的新鮮的橘子，在 BFS 時，只要有一個橘子壞掉了，我們就減一；最後只要判斷，如果新鮮的橘子沒了，就是所有的橘子都感染完成了。

這個計數器還有一個附帶好處：它讓主迴圈可以寫成 while queue and fresh_oranges > 0，一旦沒有新鮮橘子就立刻停下來 —— 這正好解決下面那個 off-by-one。

最後一步的 off-by-one

最後有一個地方要注意，那就是到了最後一步，我們會放進去的是壞掉的橘子，這樣會讓 BFS 多走一步。有兩個方法可以選擇：

在做 BFS 的同時，也要確保還有新鮮的橘子 while queue and fresh_oranges > 0。這樣也合理 —— 如果已經沒有新鮮的橘子了，就不需要再探索了。
不要加上上面的條件，直接在最後 return mins - 1 就好。

兩種都能通過（我兩種都測過）。方法 1 比較好，因為它的意思是「沒事做了就停」，讀起來就是那個意思；方法 2 的 -1 要讀者自己回想「因為最後一層只是把已經爛掉的橘子拿出來看了一遍」。

解題方向

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        queue = deque()
        fresh_oranges = 0

        for row in range(rows):
            for col in range(cols):
                if grid[row][col] == 2:
                    queue.append((row, col))      # 所有爛橘子都是起點
                elif grid[row][col] == 1:
                    fresh_oranges += 1

        directions = [(1,0), (-1,0), (0,1), (0,-1)]
        mins = 0

        if not queue and fresh_oranges > 0:
            return -1

        if fresh_oranges == 0:
            return mins

        # BFS 
        while queue and fresh_oranges > 0:            
            mins += 1
            for _ in range(len(queue)):
                row, col = queue.popleft()
                for dr, dc in directions:
                    next_row = row + dr
                    next_col = col + dc
                    if 0 <= next_row < rows and 0 <= next_col < cols: 
                        if grid[next_row][next_col] == 1:
                            queue.append((next_row, next_col))
                            grid[next_row][next_col] = 2
                            fresh_oranges -= 1

        return mins if fresh_oranges == 0 else -1

for _ in range(len(queue)) 先把這一層的數量固定下來，才能一次處理一整層 —— mins 就是層數。這一行是所有「要數幾步 / 幾分鐘」的 BFS 的共同骨架。

那兩個提前 return 其實是多餘的。 主迴圈的條件已經涵蓋了：沒有爛橘子時 queue 是空的，迴圈不會進去，最後 return mins if fresh_oranges == 0 else -1 剛好回 -1；沒有新鮮橘子時同理回 0。拿掉它們答案完全一樣 —— 留著不是錯，是「把邊界寫明」的風格選擇。

補充

和 286. Walls and Gates 一起看。 兩題都是多源 BFS，起點都是「進迴圈之前全部先入列」，但有一個關鍵差異：

	距離 / 時間存在哪	要不要 `for _ in range(len(queue))`
994 這題	要回傳「幾分鐘」，沒有地方存	要，靠外層迴圈數層數
286 Walls and Gates	直接寫進格子裡（`rooms[r][c] + 1`）	不用，讀父格子就有

所以「多源」和「要不要分層」是兩件不相干的事：多源是起點怎麼放，分層是需不需要外部計數器。

其他網格 BFS/DFS：200. Number of Islands（只要連通性，不要距離）、1091. Shortest Path in Binary Matrix（單一起點終點）、417. Pacific Atlantic Water Flow（從邊界往內灌）。骨架見 BFS / DFS 模板。

複雜度

多源 BFS

時間 $O (m n)$ — 建立起點掃一遍，之後每格最多入列、出列各一次
空間 $O (m n)$ — 佇列最壞情況（整張網格一開始都是爛橘子）

每顆爛橘子各跑一次 BFS（不要這樣做）

時間 $O (k \cdot m n)$ — k 是爛橘子的數量
空間 $O (m n)$ — 而且還要多一個距離陣列來取 min

其中 m、n 是網格的列數和行數，k 是一開始的爛橘子數。狀態直接改在 grid 上（新鮮變成爛的），所以不需要額外的 visited。