---
title: "994. Rotting Oranges"
url: "https://laigary.com/interview/coding/994-rotting-oranges"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-07-26"
tags: ["Graph", "Breadth-First Search"]
---

# 994. Rotting Oranges

[994\. Rotting Oranges](https://leetcode.com/problems/rotting-oranges/)

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

## 思路

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

### 先確定邊界

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

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

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

### 為什麼一定要多源

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

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

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

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

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

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

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

### 最後一步的 off-by-one

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

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

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

## 解題方向

```python
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](/interview/coding/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](/interview/coding/200-number-of-islands)（只要連通性，不要距離）、[1091. Shortest Path in Binary Matrix](/interview/coding/1091-shortest-path-in-binary-matrix)（單一起點終點）、[417. Pacific Atlantic Water Flow](/interview/coding/417-pacific-atlantic-water-flow)（從邊界往內灌）。骨架見 [BFS / DFS 模板](/interview/coding/bfs-dfs-template)。

## 複雜度

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

**每顆爛橘子各跑一次 BFS（不要這樣做）**
- 時間 $O(k \cdot mn)$ — `k` 是爛橘子的數量
- 空間 $O(mn)$ — 而且還要多一個距離陣列來取 min

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