LeetCode 994: Rotting Oranges (Multi-Source BFS)
LeetCode 994GraphBFSInterviewToday we solve LeetCode 994 - Rotting Oranges.
Source: https://leetcode.com/problems/rotting-oranges/
English
Problem Summary
You are given a grid where 0 means empty cell, 1 means fresh orange, and 2 means rotten orange. Every minute, any fresh orange adjacent (4-directionally) to a rotten orange becomes rotten. Return the minimum minutes to rot all oranges, or -1 if impossible.
Key Insight
This is a classic multi-source BFS. All initially rotten oranges are starting points at minute 0. BFS level-by-level naturally models “one minute per wave”.
Brute Force and Limitations
A brute simulation scans the whole grid each minute, marks newly rotten oranges, and repeats until stable. This repeatedly rescans unchanged cells, causing unnecessary overhead. In worst cases it approaches O((mn)^2).
Optimal Algorithm Steps
1) Traverse grid once: count fresh oranges and enqueue all rotten positions.
2) If fresh count is 0, return 0 immediately.
3) Run BFS by levels; each level is one minute.
4) For each rotten cell, try 4 neighbors. If neighbor is fresh, rot it, decrement fresh count, enqueue it.
5) After BFS, return minutes if fresh count is 0; otherwise return -1.
Complexity Analysis
Time: O(mn), each cell is processed at most once.
Space: O(mn) in worst case for queue.
Common Pitfalls
- Incrementing minute for every node instead of every BFS level.
- Forgetting the early return when no fresh oranges exist.
- Not decrementing fresh count when rotting neighbors.
- Revisiting already rotten cells without state checks.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int orangesRotting(int[][] grid) {
int m = grid.length, n = grid[0].length;
Deque<int[]> q = new ArrayDeque<>();
int fresh = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) q.offer(new int[]{i, j});
else if (grid[i][j] == 1) fresh++;
}
}
if (fresh == 0) return 0;
int minutes = 0;
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
while (!q.isEmpty()) {
int size = q.size();
boolean rottedThisRound = false;
for (int s = 0; s < size; s++) {
int[] cur = q.poll();
int r = cur[0], c = cur[1];
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nr >= m || nc < 0 || nc >= n || grid[nr][nc] != 1) {
continue;
}
grid[nr][nc] = 2;
fresh--;
q.offer(new int[]{nr, nc});
rottedThisRound = true;
}
}
if (rottedThisRound) minutes++;
}
return fresh == 0 ? minutes : -1;
}
}func orangesRotting(grid [][]int) int {
m, n := len(grid), len(grid[0])
type Pair struct{ r, c int }
q := []Pair{}
fresh := 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == 2 {
q = append(q, Pair{i, j})
} else if grid[i][j] == 1 {
fresh++
}
}
}
if fresh == 0 {
return 0
}
dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
minutes := 0
for len(q) > 0 {
size := len(q)
rottedThisRound := false
for s := 0; s < size; s++ {
cur := q[0]
q = q[1:]
r, c := cur.r, cur.c
for _, d := range dirs {
nr, nc := r+d[0], c+d[1]
if nr < 0 || nr >= m || nc < 0 || nc >= n || grid[nr][nc] != 1 {
continue
}
grid[nr][nc] = 2
fresh--
q = append(q, Pair{nr, nc})
rottedThisRound = true
}
}
if rottedThisRound {
minutes++
}
}
if fresh == 0 {
return minutes
}
return -1
}class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
int m = (int)grid.size(), n = (int)grid[0].size();
queue<pair<int,int>> q;
int fresh = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 2) q.push({i, j});
else if (grid[i][j] == 1) fresh++;
}
}
if (fresh == 0) return 0;
int minutes = 0;
int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
while (!q.empty()) {
int size = (int)q.size();
bool rottedThisRound = false;
for (int s = 0; s < size; ++s) {
auto [r, c] = q.front();
q.pop();
for (auto& d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nr >= m || nc < 0 || nc >= n || grid[nr][nc] != 1) continue;
grid[nr][nc] = 2;
fresh--;
q.push({nr, nc});
rottedThisRound = true;
}
}
if (rottedThisRound) minutes++;
}
return fresh == 0 ? minutes : -1;
}
};from collections import deque
from typing import List
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
q = deque()
fresh = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 2:
q.append((i, j))
elif grid[i][j] == 1:
fresh += 1
if fresh == 0:
return 0
minutes = 0
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
while q:
size = len(q)
rotted_this_round = False
for _ in range(size):
r, c = q.popleft()
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if not (0 <= nr < m and 0 <= nc < n) or grid[nr][nc] != 1:
continue
grid[nr][nc] = 2
fresh -= 1
q.append((nr, nc))
rotted_this_round = True
if rotted_this_round:
minutes += 1
return minutes if fresh == 0 else -1var orangesRotting = function(grid) {
const m = grid.length, n = grid[0].length;
const q = [];
let fresh = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 2) q.push([i, j]);
else if (grid[i][j] === 1) fresh++;
}
}
if (fresh === 0) return 0;
const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
let minutes = 0;
let head = 0;
while (head < q.length) {
const size = q.length - head;
let rottedThisRound = false;
for (let s = 0; s < size; s++) {
const [r, c] = q[head++];
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) continue;
grid[nr][nc] = 2;
fresh--;
q.push([nr, nc]);
rottedThisRound = true;
}
}
if (rottedThisRound) minutes++;
}
return fresh === 0 ? minutes : -1;
};中文
题目概述
给定一个网格：0 表示空格，1 表示新鲜橘子，2 表示腐烂橘子。每分钟，和腐烂橘子四联通相邻的新鲜橘子都会腐烂。求让所有橘子腐烂的最少分钟数；若无法全部腐烂，返回 -1。
核心思路
这是典型的多源 BFS：所有初始腐烂橘子同时作为第 0 分钟起点。BFS 的“按层扩散”正好对应“每分钟传播一层”。
暴力解法与不足
暴力做法是每分钟完整扫描整张网格，找会被腐烂的橘子并更新，再重复扫描。问题是大量重复扫描不变区域，最坏可接近 O((mn)^2)。
最优算法步骤
1）先遍历网格：统计新鲜橘子数，并把所有腐烂橘子入队。
2）若新鲜数为 0，直接返回 0。
3）按 BFS 分层处理，每层代表 1 分钟。
4）弹出当前层每个腐烂点，尝试四个方向；遇到新鲜橘子就腐烂、计数减一并入队。
5）BFS 结束后，若新鲜数归零返回分钟数，否则返回 -1。
复杂度分析
时间复杂度：O(mn)，每个格子最多处理一次。
空间复杂度：O(mn)，队列最坏可能装下大量格子。
常见陷阱
- 把“分钟数”按节点累加，而不是按层累加。
- 忘记处理“本来就没有新鲜橘子”的 0 返回。
- 腐烂后忘记 fresh--，导致结果错误。
- 没有检查状态，重复处理已腐烂格子。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int orangesRotting(int[][] grid) {
int m = grid.length, n = grid[0].length;
Deque<int[]> q = new ArrayDeque<>();
int fresh = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) q.offer(new int[]{i, j});
else if (grid[i][j] == 1) fresh++;
}
}
if (fresh == 0) return 0;
int minutes = 0;
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
while (!q.isEmpty()) {
int size = q.size();
boolean rottedThisRound = false;
for (int s = 0; s < size; s++) {
int[] cur = q.poll();
int r = cur[0], c = cur[1];
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nr >= m || nc < 0 || nc >= n || grid[nr][nc] != 1) {
continue;
}
grid[nr][nc] = 2;
fresh--;
q.offer(new int[]{nr, nc});
rottedThisRound = true;
}
}
if (rottedThisRound) minutes++;
}
return fresh == 0 ? minutes : -1;
}
}func orangesRotting(grid [][]int) int {
m, n := len(grid), len(grid[0])
type Pair struct{ r, c int }
q := []Pair{}
fresh := 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == 2 {
q = append(q, Pair{i, j})
} else if grid[i][j] == 1 {
fresh++
}
}
}
if fresh == 0 {
return 0
}
dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
minutes := 0
for len(q) > 0 {
size := len(q)
rottedThisRound := false
for s := 0; s < size; s++ {
cur := q[0]
q = q[1:]
r, c := cur.r, cur.c
for _, d := range dirs {
nr, nc := r+d[0], c+d[1]
if nr < 0 || nr >= m || nc < 0 || nc >= n || grid[nr][nc] != 1 {
continue
}
grid[nr][nc] = 2
fresh--
q = append(q, Pair{nr, nc})
rottedThisRound = true
}
}
if rottedThisRound {
minutes++
}
}
if fresh == 0 {
return minutes
}
return -1
}class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
int m = (int)grid.size(), n = (int)grid[0].size();
queue<pair<int,int>> q;
int fresh = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 2) q.push({i, j});
else if (grid[i][j] == 1) fresh++;
}
}
if (fresh == 0) return 0;
int minutes = 0;
int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
while (!q.empty()) {
int size = (int)q.size();
bool rottedThisRound = false;
for (int s = 0; s < size; ++s) {
auto [r, c] = q.front();
q.pop();
for (auto& d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nr >= m || nc < 0 || nc >= n || grid[nr][nc] != 1) continue;
grid[nr][nc] = 2;
fresh--;
q.push({nr, nc});
rottedThisRound = true;
}
}
if (rottedThisRound) minutes++;
}
return fresh == 0 ? minutes : -1;
}
};from collections import deque
from typing import List
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
q = deque()
fresh = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 2:
q.append((i, j))
elif grid[i][j] == 1:
fresh += 1
if fresh == 0:
return 0
minutes = 0
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
while q:
size = len(q)
rotted_this_round = False
for _ in range(size):
r, c = q.popleft()
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if not (0 <= nr < m and 0 <= nc < n) or grid[nr][nc] != 1:
continue
grid[nr][nc] = 2
fresh -= 1
q.append((nr, nc))
rotted_this_round = True
if rotted_this_round:
minutes += 1
return minutes if fresh == 0 else -1var orangesRotting = function(grid) {
const m = grid.length, n = grid[0].length;
const q = [];
let fresh = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 2) q.push([i, j]);
else if (grid[i][j] === 1) fresh++;
}
}
if (fresh === 0) return 0;
const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
let minutes = 0;
let head = 0;
while (head < q.length) {
const size = q.length - head;
let rottedThisRound = false;
for (let s = 0; s < size; s++) {
const [r, c] = q[head++];
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) continue;
grid[nr][nc] = 2;
fresh--;
q.push([nr, nc]);
rottedThisRound = true;
}
}
if (rottedThisRound) minutes++;
}
return fresh === 0 ? minutes : -1;
};
Comments