LeetCode 994. 腐烂的橘子
目录
题目描述
题意分析
网格里 0 表示空格子，1 表示新鲜橘子，2 表示腐烂橘子。每过一分钟，每个腐烂橘子会把它上下左右四个方向上的新鲜橘子也变成腐烂。要求返回「所有新鲜橘子都腐烂」所需要的最少分钟数，如果永远做不到就返回 -1。
第一个约束信号是「每分钟」这三个字：时间是同步推进的，一分钟内所有腐烂橘子同时向外扩散一步，起点不止一个，所以这是一个多源同时扩散的过程，而不是从某一个橘子单独出发。如果换成对每个腐烂橘子分别扩散再取最小值，就把「同时」这个前提破坏掉了。
第二个信号是「最少分钟数」：每个新鲜橘子实际腐烂的时刻，是它到任意一个腐烂源的最短步数；而整体答案是所有新鲜橘子腐烂时刻里的最大值，也就是多源扩散一共推进了多少层。
边界情况有两类，都必须单独想清楚。一是网格里一开始就没有新鲜橘子（比如全是空格或全是腐烂），此时零分钟就已经满足要求，答案是 0 而不是 -1；二是某些新鲜橘子被空格完全包围、和所有腐烂源不连通，扩散结束后它还在，这时才返回 -1。因此扩散跑完之后，必须再检查一次是否还有新鲜橘子剩下。
解法：多源 BFS 分层扩散
核心思路
腐烂过程是从所有初始腐烂橘子同时向四周扩散的等权最短路，因此使用多源 BFS：先把所有值为 2 的格子入队，它们共同组成第 0 分钟；之后每处理一层，时间推进 1 分钟，新感染的橘子进入下一层。
第一遍扫描同时统计新鲜橘子数
fresh。感染邻居时立即把 1 改成 2，并执行fresh--，这既记录状态又防止同一个格子被多个方向重复入队。BFS 结束后，fresh == 0说明全部可达；否则剩余橘子与所有腐烂源不连通，返回 -1。分层不变量是：每轮开始时，队列中的前
size个元素恰好是在同一分钟已经腐烂、将在下一分钟向外扩散的橘子。固定size后只处理这一批，新入队元素留到下一轮，所以每轮只增加 1 分钟。分钟边界要特别注意：循环条件写成「队列非空且仍有新鲜橘子」。若初始
fresh == 0，循环一次也不执行，答案是 0；若最后一层刚好感染完全部橘子，fresh > 0变为假，不会再空转并多算一分钟。
解题步骤
- 扫描网格：新鲜橘子计入
fresh，所有腐烂橘子加入队列。- 当队列非空且
fresh > 0时，记录当前队列长度size，它就是本分钟参与扩散的橘子数。- 弹出恰好
size个格子，检查四个方向；遇到新鲜橘子就立即标记为 2、减少fresh并入队。- 当前层处理完后令
minutes++。- 循环结束后，若
fresh == 0返回分钟数，否则返回 -1。对
[[2,1,1],[1,1,0],[0,1,1]]，各层新腐烂橘子的距离依次为 1、2、3、4，最后一个橘子在第 4 分钟腐烂，因此答案是 4。
代码实现
import java.util.ArrayDeque;
import java.util.Queue;
class Solution {
public int orangesRotting(int[][] grid) {
int rows = grid.length;
int cols = grid[0].length;
Queue<int[]> queue = new ArrayDeque<>();
int fresh = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == 1) {
fresh++;
} else if (grid[r][c] == 2) {
queue.offer(new int[]{r, c});
}
}
}
int minutes = 0;
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!queue.isEmpty() && fresh > 0) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] cur = queue.poll();
for (int[] dir : dirs) {
int nr = cur[0] + dir[0];
int nc = cur[1] + dir[1];
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || grid[nr][nc] != 1) {
continue;
}
grid[nr][nc] = 2;
fresh--;
queue.offer(new int[]{nr, nc});
}
}
minutes++;
}
return fresh == 0 ? minutes : -1;
}
}
func orangesRotting(grid [][]int) int {
rows := len(grid)
cols := len(grid[0])
queue := make([][2]int, 0)
fresh := 0
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
if grid[r][c] == 1 {
fresh++
} else if grid[r][c] == 2 {
queue = append(queue, [2]int{r, c})
}
}
}
dirs := [][]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
minutes := 0
for len(queue) > 0 && fresh > 0 {
size := len(queue)
for i := 0; i < size; i++ {
cur := queue[0]
queue = queue[1:]
for _, dir := range dirs {
nr := cur[0] + dir[0]
nc := cur[1] + dir[1]
if nr < 0 || nr >= rows || nc < 0 || nc >= cols || grid[nr][nc] != 1 {
continue
}
grid[nr][nc] = 2
fresh--
queue = append(queue, [2]int{nr, nc})
}
}
minutes++
}
if fresh == 0 {
return minutes
}
return -1
}
复杂度分析
- 时间复杂度：$O(mn)$，每个格子至多扫描一次、入队一次，出队后只检查四个方向。
- 空间复杂度：$O(mn)$，最坏情况下队列可同时保存整张网格中的格子。
关键点总结
- 多个初始腐烂橘子必须同时入队，它们共同构成多源 BFS 的第 0 层。
- 每层对应一分钟，固定本层
size才不会把刚感染的橘子提前用于同一分钟继续传播。- 入队时立即把 1 改为 2，既完成感染又充当访问标记，无需额外
visited。fresh同时承担提前结束和不可达判断：初始为 0 返回 0，BFS 后仍大于 0 返回 -1。- 若传播边权不再都是一分钟，普通 BFS 就不适用，应改用按到达时间排序的最短路算法。
易错点总结
- 初始没有新鲜橘子时答案是 0，不是 -1；此时无需传播。
- 不固定
size会在同一轮继续处理新入队节点，把多分钟传播压成一分钟。- 循环不加
fresh > 0，可能在全部感染后多处理最后一层，分钟数多 1。- 感染后不立即改成 2，会被其他相邻橘子重复入队并重复减少
fresh。- BFS 结束后必须检查
fresh；队列为空也可能是存在被空格隔开的新鲜橘子。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 200. 岛屿数量 | 中等 | 网格连通块计数 |
| 130. 被围绕的区域 | 中等 | 从边界反向染色 |
| 286. 墙与门 | 中等 | 多源 BFS 填充最近距离 |
| 417. 太平洋大西洋水流问题 | 中等 | 双起点集合求交 |
| 542. 01 矩阵 | 中等 | 多源 BFS 求每格最近零 |
| 1162. 地图分析 | 中等 | 多源 BFS 求最远距离 |