Rotting Oranges
題目描述
給定一個 m×n 的網格，0 是空格，1 是新鮮橘子，2 是腐爛橘子。每分鐘，腐爛橘子的四鄰新鮮橘子會變腐爛。回傳所有橘子變爛的最少分鐘數，若不可能回傳 -1。
輸入: grid = [[2,1,1],[1,1,0],[0,1,1]]
輸出: 4
輸入: grid = [[2,1,1],[0,1,1],[1,0,1]]
輸出: -1
解釋: 左下角的橘子永遠不會爛
解題思路
1
收集所有爛橘子
掃描網格，把所有 2 的位置加入 Queue，同時計數新鮮橘子
2
多源 BFS
所有爛橘子同時開始擴散
3
每一輪 = 一分鐘
處理 Queue 中當前層的所有爛橘子
4
感染鄰居
四方向的新鮮橘子變爛，加入 Queue
5
檢查結果
新鮮橘子數量 == 0？是→回傳分鐘數，否→-1
程式碼
C#
csharp
public class Solution {
public int OrangesRotting(int[][] grid) {
int m = grid.Length, n = grid[0].Length;
var queue = new Queue<(int r, int c)>();
int fresh = 0;
// 收集所有爛橘子，計數新鮮橘子
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == 2) queue.Enqueue((r, c));
else if (grid[r][c] == 1) fresh++;
}
}
if (fresh == 0) return 0;
int[][] dirs = { new[]{0,1}, new[]{0,-1}, new[]{1,0}, new[]{-1,0} };
int minutes = 0;
while (queue.Count > 0 && fresh > 0) {
minutes++;
int size = queue.Count;
for (int i = 0; i < size; i++) {
var (r, c) = queue.Dequeue();
foreach (var d in dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1) {
grid[nr][nc] = 2;
fresh--;
queue.Enqueue((nr, nc));
}
}
}
}
return fresh == 0 ? minutes : -1;
}
}TypeScript
typescript
function orangesRotting(grid: number[][]): number {
const m = grid.length, n = grid[0].length;
const queue: [number, number][] = [];
let fresh = 0;
for (let r = 0; r < m; r++) {
for (let c = 0; c < n; c++) {
if (grid[r][c] === 2) queue.push([r, c]);
else if (grid[r][c] === 1) fresh++;
}
}
if (fresh === 0) return 0;
const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]];
let minutes = 0;
while (queue.length > 0 && fresh > 0) {
minutes++;
const size = queue.length;
for (let i = 0; i < size; i++) {
const [r, c] = queue.shift()!;
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] === 1) {
grid[nr][nc] = 2;
fresh--;
queue.push([nr, nc]);
}
}
}
}
return fresh === 0 ? minutes : -1;
}Python
python
from collections import deque
def orangesRotting(grid: list[list[int]]) -> int:
m, n = len(grid), len(grid[0])
queue = deque()
fresh = 0
for r in range(m):
for c in range(n):
if grid[r][c] == 2:
queue.append((r, c))
elif grid[r][c] == 1:
fresh += 1
if fresh == 0:
return 0
dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
minutes = 0
while queue and fresh > 0:
minutes += 1
for _ in range(len(queue)):
r, c = queue.popleft()
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
grid[nr][nc] = 2
fresh -= 1
queue.append((nr, nc))
return minutes if fresh == 0 else -1複雜度分析
| | Time | Space | |--|------|-------| | 本解法 | O(m × n) | O(m × n) |
圖解
t=0: 爛[0,0]
1 分鐘→
t=1: [0,1],[1,0] 爛
1 分鐘→
t=2: [0,2],[1,1] 爛
1 分鐘→
t=3: [2,1] 爛
1 分鐘→
t=4: [2,2] 爛
進階觀點
💡面試追問
多源 BFS vs 單源 BFS：單源 BFS 從一個起點擴散，多源 BFS 從所有起點同時擴散。概念上等於加了一個虛擬超級源點連接所有真正的起點。
邊界條件：沒有新鮮橘子時直接回傳 0（不是 -1）。這是常見的 edge case 陷阱。
變體題：LC 286 Walls and Gates（多源 BFS 求距離）、LC 1162 As Far from Land as Possible。
理解測驗
🤔 為什麼所有爛橘子要同時放入 Queue，而不是一個一個處理？
🤔 如果一開始就沒有新鮮橘子，答案是什麼？