题目
LC 994 腐烂的橘子：给你一个
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 被 0 隔开，永远烂不到）
三个题面细节先钉死：
空格（0）不传播，腐烂只能发生在新鲜橘子上；扩散是
每分钟一轮、所有腐烂橘子同时发生（不是排队一个个来）；
[[0,2]] 这种没有新鲜橘子的网格 → 输出
0（不需要任何时间）。
这题的骨架一句话：
所有腐烂橘子同时出发做 BFS，向外扩圈；每分钟一层，扩完数层数 —— 这就是「多源 BFS」。
而它比单源 BFS 多出来的那个
思维开关，值得单独说清楚：
把所有腐烂橘子一起入队当「第 0 层」，BFS 的「先到的一定最近」性质会自动算出每个格子到最近源的距离 —— 腐烂时间 = 到最近源的距离，答案 = 全场最大距离。
一、核心洞察：多源 BFS = 所有源同时出发的距离场
把每个格子看成图上的点，相邻（上下左右）就有一条边。
腐烂从所有 2 同时开始蔓延，所以每个新鲜橘子变烂的时刻，就是
它到最近那个 2 的边数。这是最短路径问题，只不过源不止一个：
- 多源：初始时把所有腐烂橘子一起塞进队列（它们是第 0 分钟），然后照常做 BFS；
- 一次就够：BFS 按层推进，「第一次访问」的层数就是到最近源的距离 —— 不需要对每个源各跑一遍再取
min；
- 答案：没有新鲜橘子剩余时，最后的层数就是答案。
代码骨架：
from collections import deque
def orangesRotting(grid):
m, n = len(grid), len(grid[0])
q = deque()
fresh = 0
for r in range(m):
for c in range(n):
if grid[r][c] == 2:
q.append((r, c)) # 所有源一起入队
elif grid[r][c] == 1:
fresh += 1
minute = 0
while q and fresh:
for _ in range(len(q)): # 固定本层 = 第 minute+1 分钟要扩散的格子
r, c = q.popleft()
for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
grid[nr][nc] = 2 # 入队即标记
fresh -= 1
q.append((nr, nc))
minute += 1
return minute if fresh == 0 else -1
三个细节决定成败：
- 初始就把所有
2 入队。只入队一个源是本题第一大坑：别的源会晚好几拍才开始扩散，答案偏大甚至直接错。
for _ in range(len(q)) 固定一层。进入循环时先记下本层长度，循环只处理这么多 —— 新入队的格子属于下一分钟；minute += 1 写在整层处理完之后。- 入队即标记（
grid[nr][nc] = 2）+ fresh 计数。前者防止同一格被多个邻居重复入队；后者是 -1 判定和提前退出的依据。
二、分钟数的三种记账：层序循环 / 队列存时间戳 / 距离场
同一台多源 BFS，可以换三种记账方式，语义完全一样：
写法 A：层序循环（上面的骨架）—— 用
for _ in range(len(q)) 把「一层」切出来，
minute 在层外 +1。
写法 B：队列存时间戳 —— 不切层，把
(r, c, t) 一起入队：
def orangesRotting_ts(grid):
m, n = len(grid), len(grid[0])
q = deque()
fresh = 0
for r in range(m):
for c in range(n):
if grid[r][c] == 2:
q.append((r, c, 0))
elif grid[r][c] == 1:
fresh += 1
answer = 0
while q and fresh:
r, c, t = q.popleft()
for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
grid[nr][nc] = 2
fresh -= 1
answer = max(answer, t + 1) # 关键：入队时就把时间戳记进答案
q.append((nr, nc, t + 1))
return answer if fresh == 0 else -1
它有个隐蔽的坑：
answer 必须在
入队时更新 —— 如果写在「弹出处」，
fresh 清零提前退出后，
最后一批入队的时间戳还没被弹出、没被计入，答案会差 1。
写法 C：距离场（动画二的视角）—— 直接开一张
stamp 表，每个格子第一次被访问时把当前分钟写进去：
def orangesRotting_dist(grid):
m, n = len(grid), len(grid[0])
stamp = [[None] * n for _ in range(m)]
q = deque()
fresh = 0
for r in range(m):
for c in range(n):
if grid[r][c] == 2:
stamp[r][c] = 0
q.append((r, c))
elif grid[r][c] == 1:
fresh += 1
minute = 0
while q and fresh:
minute += 1
for _ in range(len(q)):
r, c = q.popleft()
for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
grid[nr][nc] = 2
stamp[nr][nc] = minute # 盖章：腐烂时刻 = 到最近源的距离
fresh -= 1
q.append((nr, nc))
if fresh > 0:
return -1
return max((v for row in stamp for v in row if v is not None), default=0)
收尾的
max(..., default=0) 兜住「一个橘子都没有」的网格（没有源时表里全是
None）。这张表的每个数字都等于
到最近源的距离 —— 它是「多源 BFS 不变量」的具象化：每个格子只盖一次章、先到的一定最近。
三者对比：
三、动画怎么看
动画一（
algo-viz--lc994）：
多源 BFS 分层扩散。左边是网格（绿 = 新鲜、金 = 腐烂、浅 = 空，小圆点 = 初始腐烂的「源」）；右上三块面板：当前
分钟数、
剩余新鲜 fresh、
队列（待扩散）。帧分两种：
layer 帧亮出本分钟要处理的整层（金框），
rot 帧展示扩散结果 —— 新腐烂的格子（浅金 + 绿框）进入下一层队列，fresh 减少。盯住三件事：
源不止一个（第 0 分钟队列里就有好几个格子）、
分钟数只在整层处理完后才 +1、以及
fresh 的变化。
动画二（
algo-viz--lc994dist）：
腐烂时刻表（距离场）。同一张网格、同一台 BFS，但换一种记账：每个格子第一次被访问时被盖上「腐烂时刻」的章 —— 源 = 0，之后每分钟盖一批。跑完时整张表就是
到最近源的距离场，右下角面板里的
max(stamp) 就是答案。把它和动画一对照看：
动画一数的是「第几分钟」，动画二写的是「每格的值」 —— 同一件事的两种记法。
四、完整推演表
动画一（分层队列）：网格
六块新鲜橘子，唯一源
(0,0)。逐帧如下：
两个容易看漏的点：第 2 分钟里
(1,1) 被
(0,1) 腐烂后，
(1,0) 再检查它时它已经不是新鲜橘子了 ——
同一分钟内不会重复腐烂；而
(2,2) 只有一条路
(2,1) → (2,2)，所以它的时刻是第 4 分钟（不是离
(0,0) 的直线距离）。
动画二（腐烂时刻表）：同一张网格，每格盖「腐烂时刻」的章：
跑完的章表：
每个数字都是「到最近源的距离」，
· 是空格。一眼能看出
(1,1) 的时刻是 2 而不是 min(1+1, 1+1) 之外的东西 —— BFS 说的算：这张表就是最终答案的可视化。
五、-1 与提前退出：fresh 计数
为什么代码里要维护
fresh 而不是最后遍历一遍网格？两个理由：
- 提前退出：
while q and fresh —— fresh 一清零就停，省掉「队列里还剩最后一层尾巴」的无谓处理；
- -1 判定：循环结束时
fresh > 0，说明有新鲜橘子被空格隔开、BFS 够不到 —— 返回 -1。
注意判据的正确形式是
「BFS 结束后 fresh 仍大于 0」，不是「队列空了」：
- 队列空了 +
fresh == 0 → 正常结束，返回 minute；
- 队列空了 +
fresh > 0 → 有够不到的橘子，返回 -1。
另一个细节：最后一个能腐烂的批次处理完、fresh 清零时，
minute 不要再空转加一轮 —— 层循环的结构天然保证这一点（
minute += 1 在层后，循环条件先看 fresh）。如果你想省掉层结构，用写法 B 的时间戳，答案就是「最后一个被弹出/入队的时间戳」。
六、Java 版
class Solution {
private static final int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public int orangesRotting(int[][] grid) {
int m = grid.length, n = grid[0].length;
int fresh = 0, minute = 0;
Deque<int[]> queue = new ArrayDeque<>();
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == 2) queue.offer(new int[]{r, c}); // 所有源入队
else if (grid[r][c] == 1) fresh++;
}
}
while (!queue.isEmpty() && fresh > 0) {
for (int size = queue.size(); size > 0; size--) { // 固定本层
int[] cur = queue.poll();
for (int[] d : DIRS) {
int nr = cur[0] + d[0], nc = cur[1] + d[1];
if (nr < 0 || nr >= m || nc < 0 || nc >= n || grid[nr][nc] != 1) continue;
grid[nr][nc] = 2; // 入队即标记
fresh--;
queue.offer(new int[]{nr, nc});
}
}
minute++;
}
return fresh == 0 ? minute : -1;
}
}
两个 Java 专属注意点：
for (int size = queue.size(); size > 0; size--) 必须
先把 size 记下来 —— 直接在条件里写
queue.size() 会把新入队的下一层也算进来，层就切错了；以及原地改
grid 前想清楚——如果输入不能改（有些平台多组用例复用），就换成一张
visited 布尔表。
七、同族题：542 / 1091 / 1162 / 934 / 1765 / 286
994 是「网格 + 多源 BFS 距离场」这一族的原点，换个包装就是一条完整题链：
- LC 542 01 矩阵：求每个格子到最近的
0 的距离 —— 把「0」当源，和 994 一模一样的多源 BFS 距离场；
- LC 1091 二进制矩阵中的最短路：单源到单目标的八方向最短路 —— 多源的「反面」；
- LC 1162 地图分析：离最近陆地最远的海格 —— 多源 BFS 后取 max（和 994 的答案口径一致）；
- LC 934 最短的桥：先用 DFS 给第一座岛染色，再从它的所有格子做多源 BFS 找第二座岛 —— 先 1 后 1 的两次搜索；
- LC 1765 地图中的最高点：从所有水域出发做多源 BFS 生成高度场 —— 源换成了水；
- LC 286 墙与门（会员）：多源 BFS 给每个房间填「到最近门的距离」，和 542 镜像。
把它们排成一列看：
多源 BFS 的模板永远是「把所有源一起入队 + 按层推进 + 每格只访问一次」；剩下的差别只在「源是谁」（腐烂橘子 / 0 / 陆地 / 水 / 门）和「最后取什么」（最后一层 / 最大距离 / 某个目标）。
八、边界情况
- 没有新鲜橘子：直接返回
0（while 条件不成立，minute 保持 0）；
- 没有腐烂橘子但有新鲜：队列为空、fresh > 0 → 返回
-1；
- 全空网格：没有源也没有新鲜 →
0；
- 源和新鲜都在，但被
0 隔开：BFS 走不过去，返回 -1；
- 只有一个格子：
[[2]] / [[0]] → 0，[[1]] → -1；
- 一条长廊：
1 × n 单行，答案 = 最远新鲜橘子的距离；
- 多个源会合：两边的源向中间扩，相遇时「先到的一定最近」自动生效，不需要特殊处理；
- 注意
minute 的起点是 0：源是「第 0 分钟」就腐烂的，第一次扩散发生后才变成 1。
九、复杂度
每个格子最多入队一次、每条邻接边最多被检查一次 —— 三者都是标准 BFS 的
O(m·n)。空间上，斐波那契式的「队列最坏有多大」有个常见答案：
一层可能同时挤满网格（全连通时），所以上界就是
O(m·n)。
十、常见坑
- 只把第一个腐烂橘子入队：多源退化成了单源，别的源「晚出发」，答案偏大甚至错。初始必须把所有
2 入队。
- 分钟数按「弹出的格子数」加：不是每个格子一分钟 —— 是每层一分钟。忘记
for _ in range(len(q)) 固定层长，分钟数直接膨胀。
- 出队才标记 / 入队不标记：同一格会被多个邻居重复入队，
fresh 被减多次。入队的那一刻就置 2。
- -1 判定写成「队列空了就 -1」：把「全烂完但队列还剩最后一层尾巴」的正常情况误判成 -1。判据是 fresh > 0。
- fresh 清零后还空转一轮：
minute 多加 1。层循环 + while q and fresh 才能自然停住。
- 把
0 当成能传播的格子：腐烂只能落到新鲜橘子上，空格是墙不是路。
- 写法 B 的时间戳更新写在「弹出」处：
fresh 清零提前退出后，最后一批入队的时间戳还没被弹出、没被计入 —— 更新要写在入队处。
minute 初值写成 1：全烂网格会返回 1 而不是 0。源是第 0 分钟。- 原地修改后复用输入：
1 → 2 破坏了网格；多组用例或多轮测试要小心。
- 把「同时扩散」写成了「串行扩散」：一个格子扩散完立刻用它的新邻居继续扩散 —— 这会把「同一分钟」的格子拍扁成不同分钟，答案偏小。
十一、面试怎么答
第一段 · 骨架：这是多源 BFS 的最短时间问题。把所有腐烂橘子初始入队（第 0 分钟），每分钟处理一整层、把新鲜邻居变腐烂并入队，同时维护
fresh 计数。BFS 结束时
fresh == 0 就返回分钟数，否则
-1。
O(m·n)。
第二段 · 主动补两个「为什么」（
这段是区分度所在）：为什么
多源而不是逐个源 BFS —— 逐源是
O(k·m·n) 还要逐格取 min，多源一次就够，因为 BFS 第一次访问的层数天然是「到最近源的距离」；为什么
不能 DFS —— 腐烂时间是
最短时间，DFS 会绕远路，给出的是某条路径的时间而不是最小时间。
第三段 · 变体与追问：这个模板可以换源、换目标、换维数 —— 542（到最近 0）、1162（离陆地最远）、1765（水域出发的高度场）、934（先染色再 BFS）；如果要求「每分钟腐烂速度不同」，BFS 就不再适用，要换成按时间排序的优先队列（类似 Dijkstra 的推广）。
追问连跳：
- 要
每格到最近 0 的距离矩阵 → LC 542，多源 BFS 直接输出距离场；
- 要
最远的格子 → LC 1162，多源 BFS 后取
max；
- 要
两座岛之间的最短桥 → LC 934，先 DFS 染色、再多源 BFS；
- 要
从水出发的高度场 → LC 1765，源是水、答案是最大高度；
- 要
带权重的腐烂时间 → 优先队列代替队列（Dijkstra 的味道）。
一句话收尾：「腐烂的橘子只有一台机器 ——
把所有源一起入队，让 BFS 按分钟分层扩圈；分钟数、时间戳、距离场是同一件事的三种记法，
fresh 计数和
-1 判定则是它唯一的安全带。」
结语
994 的全部难度浓缩在「多源」两个字上：源不止一个，所以不能只入队一个；时间按分钟走，所以要按层切；答案要么数层、要么取最大时间戳。把这三件事记牢，代码二十行，而它身后站着整个「网格距离场」题族——542 的距离矩阵、1162 的最远格子、934 的建桥、1765 的高度场，都是同一台机器换个源。
下一篇见。