腐烂的橘子
Rotting Oranges
每分钟，腐烂橘子会感染上下左右相邻的新鲜橘子；返回全部腐烂的最短分钟数，做不到返回 -1。
在力扣中练习题目描述
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
- 值
0代表空单元格； - 值
1代表新鲜橘子； - 值
2代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
示例 1：
输入：grid = [[2,1,1],[1,1,0],[0,1,1]] 输出：4
示例 2：
输入：grid = [[2,1,1],[0,1,1],[1,0,1]] 输出：-1 解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上。
示例 3：
输入：grid = [[0,2]] 输出：0 解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 10grid[i][j]仅为0、1或2
解题思路
主解法
多源 BFS · 分层扩散
所有腐烂橘子同时入队，一轮就是一分钟
如果只有一个腐烂橘子，从它出发做 BFS，层数就是分钟数。现在可能有多个腐烂源，而且它们同时扩散，所以要把所有腐烂橘子一起放进队列，做多源 BFS。
每一轮先锁定当前队列大小 sz，只处理这 sz 个节点；它们感染出的新橘子留到下一轮。这样“轮”就对应“分钟”，同一分钟内不会出现连锁感染。
分步图解
所有腐烂橘子一起入队；先统计新鲜橘子数量，最后用它判断是否有橘子永远无法腐烂。
本层待处理的腐烂橘子
← 队首出队队尾入队 ←
0,0front
3,3rear
感染时立刻把格子改成 2 并让 fresh 减一，避免同一个新鲜橘子被多个源重复入队。BFS 结束后如果 fresh 仍大于 0，说明有橘子被空格隔开，返回 -1。
分步图解
第 2 分钟：新感染 (1,1)、(2,2)、(3,1)；剩余新鲜 3 个。
- minutes
- 2
本层待处理的腐烂橘子
← 队首出队队尾入队 ←
1,1front
2,2
3,1rear
新入队 1,1、2,2、3,1
自拟网格有两个腐烂源和一个被空格包围的新鲜橘子。前三分钟能感染所有可达橘子，但右上角那个永远不变，最终返回 -1，而不是 3。
时间 O(m·n)空间 O(m·n)
易错点
- 只从一个腐烂橘子出发：其他源的最短时间被忽略。
- 不分层，直接一个 while 处理队列：分钟数无法对应层。
- 感染后不立刻标记：同一分钟可能被多个邻居重复入队。
- 只返回 minutes，不检查 fresh：不可达时应该返回 -1。
代码与演示
演示输入
grid = [[2,1,0,1],[1,1,0,0],[0,1,1,1],[1,1,1,2]]所有腐烂橘子一起入队；先统计新鲜橘子数量，最后用它判断是否有橘子永远无法腐烂。
本层待处理的腐烂橘子
← 队首出队队尾入队 ←
0,0front
3,3rear
查看 C++ 代码
延伸阅读
- 多源 BFS 的“源”可以看成超级源点的第一层；所有源同时入队，层数仍然是最短距离。
- 网格 BFS 要区分“已访问”和“可通行”：这里腐烂状态本身就是访问标记。