994. 腐烂的橘子
题目描述
输入一个 m x n 的网格 grid。0 表示空格，1 表示新鲜橘子，2 表示腐烂的橘子。
每过一分钟，所有腐烂橘子上、下、左、右相邻的新鲜橘子都会同时变成腐烂的。
返回直到网格里不剩新鲜橘子为止最少要经过的分钟数。如果总有新鲜橘子无法被传染，返回 -1。如果一开始就没有新鲜橘子，返回 0。
示例 1
输入：grid = [[2,1,1],[1,1,0],[0,1,1]] 输出：4
解释：腐烂从左上角扩散，第 4 分钟时右下角的橘子也腐烂了。
示例 2
输入：grid = [[2,1,1],[0,1,1],[1,0,1]] 输出：-1
解释：左下角 (2,0) 的橘子四周没有能传染它的橘子，永远不会腐烂。
示例 3
输入：grid = [[0,2]] 输出：0
解释：一开始就没有新鲜橘子，所以是 0 分钟。
数据范围
m == grid.lengthn == grid[i].length1 <= m, n <= 10grid[i][j]只会是0、1或2。
解题思路
多源 BFS 按分钟传播。
为什么正确
同一分钟队列属于同一层传播。
复杂度分析
时间 O(mn)，额外空间 O(mn)。
易错点
注意边界条件并在回溯或弹出后恢复状态。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
from collections import deque
class Solution:
def orangesRotting(self,g):
m,n=len(g),len(g[0]);q=deque();f=0
for r in range(m):
for c in range(n):
if g[r][c]==2:q.append((r,c))
elif g[r][c]==1:f+=1
t=0
while q and f:
for _ in range(len(q)):
r,c=q.popleft()
for dr,dc in ((1,0),(-1,0),(0,1),(0,-1)):
R,C=r+dr,c+dc
if 0<=R<m and 0<=C<n and g[R][C]==1:g[R][C]=2;f-=1;q.append((R,C))
t+=1
return t if not f else -1class Solution {
public int orangesRotting(int[][] g) {
int m = g.length, n = g[0].length; Deque<int[]> q = new ArrayDeque<>(); int f = 0;
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++) {
if (g[r][c] == 2) q.offer(new int[]{r, c});
else if (g[r][c] == 1) f++;
}
int t = 0;
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!q.isEmpty() && f > 0) {
for (int k = q.size(); k > 0; k--) {
int[] p = q.poll(); int r = p[0], c = p[1];
for (int[] d : dirs) {
int R = r + d[0], C = c + d[1];
if (0 <= R && R < m && 0 <= C && C < n && g[R][C] == 1) { g[R][C] = 2; f--; q.offer(new int[]{R, C}); }
}
}
t++;
}
return f == 0 ? t : -1;
}
}class Solution {
public:
int orangesRotting(vector<vector<int>>& g) {
int m = g.size(), n = g[0].size(); queue<pair<int, int>> q; int f = 0;
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++) {
if (g[r][c] == 2) q.push({r, c});
else if (g[r][c] == 1) f++;
}
int t = 0;
int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!q.empty() && f) {
for (int k = q.size(); k > 0; k--) {
auto [r, c] = q.front(); q.pop();
for (auto& d : dirs) {
int R = r + d[0], C = c + d[1];
if (0 <= R && R < m && 0 <= C && C < n && g[R][C] == 1) { g[R][C] = 2; f--; q.push({R, C}); }
}
}
t++;
}
return !f ? t : -1;
}
};func orangesRotting(g [][]int) int {
m, n, q, f := len(g), len(g[0]), [][2]int{}, 0
for r := 0; r < m; r++ {
for c := 0; c < n; c++ {
if g[r][c] == 2 {
q = append(q, [2]int{r, c})
} else if g[r][c] == 1 {
f++
}
}
}
t := 0
for len(q) > 0 && f > 0 {
for k := len(q); k > 0; k-- {
r, c := q[0][0], q[0][1]; q = q[1:]
for _, d := range [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}} {
R, C := r+d[0], c+d[1]
if 0 <= R && R < m && 0 <= C && C < n && g[R][C] == 1 {
g[R][C] = 2; f--; q = append(q, [2]int{R, C})
}
}
}
t++
}
if f == 0 {
return t
}
return -1
}var orangesRotting = function(g) {
const m = g.length, n = g[0].length, q = []; let f = 0;
for (let r = 0; r < m; r++)
for (let c = 0; c < n; c++) {
if (g[r][c] === 2) q.push([r, c]);
else if (g[r][c] === 1) f++;
}
let t = 0;
while (q.length && f) {
for (let k = q.length; k > 0; k--) {
const [r, c] = q.shift();
for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
const R = r + dr, C = c + dc;
if (0 <= R && R < m && 0 <= C && C < n && g[R][C] === 1) { g[R][C] = 2; f--; q.push([R, C]); }
}
}
t++;
}
return !f ? t : -1;
};function orangesRotting(g: number[][]): number {
const m = g.length, n = g[0].length, q: [number, number][] = []; let f = 0;
for (let r = 0; r < m; r++)
for (let c = 0; c < n; c++) {
if (g[r][c] === 2) q.push([r, c]);
else if (g[r][c] === 1) f++;
}
let t = 0;
while (q.length && f) {
for (let k = q.length; k > 0; k--) {
const [r, c] = q.shift()!;
for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
const R = r + dr, C = c + dc;
if (0 <= R && R < m && 0 <= C && C < n && g[R][C] === 1) { g[R][C] = 2; f--; q.push([R, C]); }
}
}
t++;
}
return !f ? t : -1;
};