LC994Medium网格多源 BFS层序扩散最短时间

腐烂的橘子

把所有初始腐烂橘子放到同一条时间起跑线。BFS 每处理完一层，才代表共同过去了一分钟。

题目是什么

新鲜橘子会被上下左右相邻的腐烂橘子感染，求全部腐烂的最少分钟。

解决什么问题

同时模拟多个传播源，并准确区分同一分钟与下一分钟。

核心结论

所有初始 2 一起入队；冻结每层队列作为一分钟，最后 fresh 未清零则返回 -1。

01交互算法精讲

先说结论：这道题到底解决什么

多个腐烂橘子同时向外传播时，怎样让程序中的队列层与现实中的一分钟严格对应，而不是按处理顺序错误计时？

中心结论：所有初始 2 一起入队；冻结每层队列作为一分钟，最后 fresh 未清零则返回 -1。

读完必须能回答

1.为什么所有初始腐烂橘子必须在时间 0 一起入队？
2.为什么每轮要先冻结队列长度，新感染的橘子不能立刻继续传播？
3.队列耗尽以后，怎样区分“全部腐烂完成”和“仍有不可达橘子”？

02交互算法精讲

完整题目与题意拆解

给定 m×n 网格：0 表示空格，1 表示新鲜橘子，2 表示腐烂橘子。每分钟，腐烂橘子会让上下左右相邻的新鲜橘子腐烂。

返回直到没有新鲜橘子所需的最少分钟。如果无论如何仍有新鲜橘子，返回 -1。

• 只允许上下左右传播，不允许对角线。
• 多个腐烂源在同一分钟同时传播。
• 初始没有新鲜橘子时答案是 0。

输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4
解释：腐烂前沿每分钟向四邻扩散，最后一个橘子在第 4 分钟腐烂。

网格中的每个橘子是一个节点，四方向相邻关系是边。腐烂从所有值为 2 的节点同时向外扩散。

问题问最少时间，等价于每个新鲜橘子到最近初始腐烂源的最短距离中的最大值。多源 BFS 正好同时计算这些最短距离。

一分钟不是“弹出一个橘子”，而是“处理完这一分钟开始时已经在队列里的全部腐烂橘子”。

动画 1 · 题意扫描

先读懂格子与同时扩散

观察 0、1、2 的含义，以及全部初始腐烂源为什么属于同一个时间 0。

Step 1/20%

2=腐烂 · 1=新鲜 · 0=空

fresh = 6

先读懂 0、1、2

发生了什么: 主例有一个初始腐烂橘子、六个新鲜橘子和两个空格。
为什么: 只有值为 1 的四邻格能发生状态变化，空格会阻断传播。
下一步: 扫描网格，把所有初始 2 放入同一个队列。

当前状态

grid

3 × 3

fresh

当前 Go 代码

1func orangesRotting(grid [][]int) int {2    rows, cols := len(grid), len(grid[0])3    queue := make([][2]int, 0)4    fresh := 05    for r := 0; r < rows; r++ { for c := 0; c < cols; c++ {6        if grid[r][c] == 2 { queue = append(queue, [2]int{r,c}) }7        if grid[r][c] == 1 { fresh++ }8    } }9    dirs := [][2]int{{1,0},{-1,0},{0,1},{0,-1}}10    minutes := 011    for fresh > 0 && len(queue) > 0 {12        size := len(queue)13        minutes++14        for i := 0; i < size; i++ {15            cell := queue[0]; queue = queue[1:]16            for _, d := range dirs { nr, nc := cell[0]+d[0], cell[1]+d[1]17                if nr<0 || nr>=rows || nc<0 || nc>=cols || grid[nr][nc]!=1 { continue }18                grid[nr][nc] = 219                fresh--20                queue = append(queue, [2]int{nr,nc})21            } }22    }23    if fresh > 0 {24        return -125    }26    return minutes27}

看完带走：题目问的是全局完成时间，不是某个源单独走了多少步。

03交互算法精讲

第一层方案：暴力做法

最直观的模拟是每分钟完整扫描网格，找到所有与 2 相邻的 1，先记录后统一腐烂，直到没有变化。

如果最多经过 O(mn) 分钟，而每分钟又扫描 O(mn) 个格子，最坏可能达到 O((mn)²)。同时还要小心不能让本分钟新腐烂的格子立刻继续传播。

repeat each minute:
  扫描所有格子并收集将腐烂的位置
  扫描结束后统一修改

BFS 队列把“本分钟的前沿”直接存下来，避免每一分钟重新检查整张网格。

动画 2 · 暴力重复

逐个源处理为什么会把同一分钟拆开

对照源点收集和第一分钟：如果一个源跑完才轮到另一个源，传播时间会依赖遍历顺序。

Step 1/30%

时间 0 · 多源初始化

queue

(0,0)

queue=[(0,0)] · fresh=6

所有初始腐烂源同时入队

发生了什么: 扫描发现 c00=2，将坐标 (0,0) 入队；fresh 统计为 6。
为什么: 多源必须共享时间 0，不能让某个源先跑完整段传播。
下一步: 冻结当前队列长度 1，开始第 1 分钟。

当前状态

minutes

queue size

当前 Go 代码

1func orangesRotting(grid [][]int) int {2    rows, cols := len(grid), len(grid[0])3    queue := make([][2]int, 0)4    fresh := 05    for r := 0; r < rows; r++ { for c := 0; c < cols; c++ {6        if grid[r][c] == 2 { queue = append(queue, [2]int{r,c}) }7        if grid[r][c] == 1 { fresh++ }8    } }9    dirs := [][2]int{{1,0},{-1,0},{0,1},{0,-1}}10    minutes := 011    for fresh > 0 && len(queue) > 0 {12        size := len(queue)13        minutes++14        for i := 0; i < size; i++ {15            cell := queue[0]; queue = queue[1:]16            for _, d := range dirs { nr, nc := cell[0]+d[0], cell[1]+d[1]17                if nr<0 || nr>=rows || nc<0 || nc>=cols || grid[nr][nc]!=1 { continue }18                grid[nr][nc] = 219                fresh--20                queue = append(queue, [2]int{nr,nc})21            } }22    }23    if fresh > 0 {24        return -125    }26    return minutes27}

看完带走：所有源共享一个队列，才能让程序顺序与现实同时扩散保持一致。

优化方向：把所有源点一次性入队，相当于添加一个虚拟超级源连接所有初始腐烂格；普通 BFS 的层数自然就是分钟。

04交互算法精讲

整体地图：先做什么，再做什么

先扫描网格完成两件事：把所有初始值为 2 的格子加入同一个队列，并统计新鲜橘子 fresh。这样队列第一层完整代表时间 0 的所有传播源。

之后按层做 BFS。每轮固定当前队列长度 size，只处理这 size 个旧前沿；它们感染的新橘子排到队尾，留给下一分钟。循环结束后用 fresh 验收结果。

• 初始化：收集全部源点并统计 fresh。
• 扩散：冻结当前层，检查上下左右四邻格。
• 验收：fresh 为 0 返回分钟数，否则返回 -1。

队列顺序只是程序执行顺序；冻结层边界才把顺序执行还原成现实中的同时发生。

05交互算法精讲

多源 BFS 的共同起跑线是什么

单源 BFS 从一个起点向外扩散，多源 BFS 只是把多个起点同时放入第 0 层。此后任意格子第一次被感染的层数，就是它离最近初始腐烂源的最短四方向距离。

若逐个源分别跑 BFS，再取最小时间，会重复扫描大量格子；若让一个源全部跑完再处理另一个源，又会破坏同时扩散。共同队列既正确表达时间，也避免重复工作。

time 0: queue=[所有初始 2]
time 1: 只处理 time 0 的队首，新增格进入队尾
time 2: 再处理上一轮新增的整层

感染格必须在入队时立刻改成 2。否则同一分钟的多个前沿可能把同一格重复加入队列。

动画 3 · 核心概念

多源队列是一条共同起跑线

观察初始源、第一层前沿和第二层前沿如何在同一条队列中分层排列。

Step 1/30%

时间 0 · 多源初始化

queue

(0,0)

queue=[(0,0)] · fresh=6

所有初始腐烂源同时入队

发生了什么: 扫描发现 c00=2，将坐标 (0,0) 入队；fresh 统计为 6。
为什么: 多源必须共享时间 0，不能让某个源先跑完整段传播。
下一步: 冻结当前队列长度 1，开始第 1 分钟。

当前状态

minutes

queue size

当前 Go 代码

1func orangesRotting(grid [][]int) int {2    rows, cols := len(grid), len(grid[0])3    queue := make([][2]int, 0)4    fresh := 05    for r := 0; r < rows; r++ { for c := 0; c < cols; c++ {6        if grid[r][c] == 2 { queue = append(queue, [2]int{r,c}) }7        if grid[r][c] == 1 { fresh++ }8    } }9    dirs := [][2]int{{1,0},{-1,0},{0,1},{0,-1}}10    minutes := 011    for fresh > 0 && len(queue) > 0 {12        size := len(queue)13        minutes++14        for i := 0; i < size; i++ {15            cell := queue[0]; queue = queue[1:]16            for _, d := range dirs { nr, nc := cell[0]+d[0], cell[1]+d[1]17                if nr<0 || nr>=rows || nc<0 || nc>=cols || grid[nr][nc]!=1 { continue }18                grid[nr][nc] = 219                fresh--20                queue = append(queue, [2]int{nr,nc})21            } }22    }23    if fresh > 0 {24        return -125    }26    return minutes27}

看完带走：一个格子的 BFS 层数，就是它被最近初始腐烂源感染的分钟。

06交互算法精讲

如何让 BFS 的一层严格等于一分钟

进入一轮前读取 `size := len(queue)`。随后只弹出 size 个位置，即使期间队列因为新增感染而变长，也不能把新增部分放进本轮继续处理。

每遇到一个值为 1 的合法四邻格，立即写成 2、执行 fresh-- 并入队。处理完这 size 个旧前沿以后，才算过去一分钟。

• 循环条件同时要求 `fresh > 0` 与队列非空。
• 只有值为 1 的格子可以被首次感染。
• fresh 变成 0 后不再启动多余一轮。

扫描初始化 queue 和 fresh。然后在 fresh>0 且 queue 非空时，分钟加一，冻结 size 并处理整层。

循环结束后，如果 fresh 仍大于 0，说明传播前沿已经耗尽但有孤立新鲜橘子，返回 -1；否则返回 minutes。

循环条件带 fresh>0 很重要：最后一个橘子腐烂后无需再处理它作为传播源的一轮，否则容易产生 off-by-one。

动画 4 · 机制构建

冻结 size，防止新感染格穿越时间

逐分钟观察队列冻结大小、fresh 变化和新格入队，确认新前沿只在下一轮工作。

Step 1/40%

第 1 分钟

queue

(0,1)(1,0)

fresh: 6 → 4

第 1 分钟：腐烂两个四邻格

发生了什么: (0,0) 感染 (0,1) 和 (1,0)，它们进入下一层队尾。
为什么: 这两个橘子是在第 1 分钟末才腐烂，不能在当前冻结层继续扩散。
下一步: 冻结新队列中的两个格子，开始第 2 分钟。

当前状态

minutes

0→1

fresh

6→4

当前 Go 代码

1func orangesRotting(grid [][]int) int {2    rows, cols := len(grid), len(grid[0])3    queue := make([][2]int, 0)4    fresh := 05    for r := 0; r < rows; r++ { for c := 0; c < cols; c++ {6        if grid[r][c] == 2 { queue = append(queue, [2]int{r,c}) }7        if grid[r][c] == 1 { fresh++ }8    } }9    dirs := [][2]int{{1,0},{-1,0},{0,1},{0,-1}}10    minutes := 011    for fresh > 0 && len(queue) > 0 {12        size := len(queue)13        minutes++14        for i := 0; i < size; i++ {15            cell := queue[0]; queue = queue[1:]16            for _, d := range dirs { nr, nc := cell[0]+d[0], cell[1]+d[1]17                if nr<0 || nr>=rows || nc<0 || nc>=cols || grid[nr][nc]!=1 { continue }18                grid[nr][nc] = 219                fresh--20                queue = append(queue, [2]int{nr,nc})21            } }22    }23    if fresh > 0 {24        return -125    }26    return minutes27}

看完带走：先冻结本层再扩散，是“一层等于一分钟”的代码基础。

07交互算法精讲

核心难点：为什么第 k 层正好对应第 k 分钟

时间 0 时，队列包含且只包含所有初始腐烂橘子。假设第 k 轮开始时，队列前 size 个元素正好是第 k-1 分钟结束时新腐烂的格子。

本轮从这些格子向四邻传播，所以新加入队列的格子恰好会在第 k 分钟腐烂；由于冻结了 size，它们不会在同一分钟再次传播。由此每一层与一分钟一一对应。

BFS 穷尽所有可从初始源到达的非空路径。若队列空时 fresh 仍大于 0，这些格子与任何初始源之间都被边界或空格阻断，因此无论等多久都不会腐烂。

minutes 统计的是完成过的传播层数，不是弹出过的橘子数量。

正确性抓手

• 所有初始腐烂格同时入队，保证时间 0 的所有源被公平处理。
• 冻结队列层后，本轮新增节点只在下一轮扩散，所以每层恰好对应一分钟。
• 队列耗尽后 fresh 是否归零，准确区分全部可达与存在孤立新鲜橘子。

08交互算法精讲

完整执行过程

观察队列冻结边界和 fresh 变化：同一分钟新感染的格子只排到队尾，必须等下一帧分钟开始才能继续传播。

1扫描主例，初始腐烂源 (0,0) 入队，统计 fresh=6，minutes=0。
2第 1 分钟冻结 size=1，感染 (0,1)、(1,0)，fresh 从 6 变 4。
3第 2 分钟只处理上一轮的两个新前沿，感染 (0,2)、(1,1)，fresh 变 2。
4第 3、4 分钟继续传播，空格 0 始终不可穿过，最后 (2,2) 腐烂并令 fresh=0。
5循环立即停止并返回 4；若换成被空格隔断的网格，队列会先耗尽并返回 -1。

动画 5 · 完整执行

四分钟传播与不可达反例完整对照

从读取网格播放到答案 4，再看队列耗尽但 fresh>0 时为什么必须返回 -1。

Step 1/90%

2=腐烂 · 1=新鲜 · 0=空

fresh = 6

先读懂 0、1、2

发生了什么: 主例有一个初始腐烂橘子、六个新鲜橘子和两个空格。
为什么: 只有值为 1 的四邻格能发生状态变化，空格会阻断传播。
下一步: 扫描网格，把所有初始 2 放入同一个队列。

当前状态

grid

3 × 3

fresh

当前 Go 代码

1func orangesRotting(grid [][]int) int {2    rows, cols := len(grid), len(grid[0])3    queue := make([][2]int, 0)4    fresh := 05    for r := 0; r < rows; r++ { for c := 0; c < cols; c++ {6        if grid[r][c] == 2 { queue = append(queue, [2]int{r,c}) }7        if grid[r][c] == 1 { fresh++ }8    } }9    dirs := [][2]int{{1,0},{-1,0},{0,1},{0,-1}}10    minutes := 011    for fresh > 0 && len(queue) > 0 {12        size := len(queue)13        minutes++14        for i := 0; i < size; i++ {15            cell := queue[0]; queue = queue[1:]16            for _, d := range dirs { nr, nc := cell[0]+d[0], cell[1]+d[1]17                if nr<0 || nr>=rows || nc<0 || nc>=cols || grid[nr][nc]!=1 { continue }18                grid[nr][nc] = 219                fresh--20                queue = append(queue, [2]int{nr,nc})21            } }22    }23    if fresh > 0 {24        return -125    }26    return minutes27}

看完带走：成功看 fresh 归零，失败看前沿耗尽；minutes 只统计真实发生的传播层。

09交互算法精讲

把动画和 Go 代码逐行对应

每一帧使用稳定的语义行 ID，不依赖容易漂移的数字行号。先观察分支为什么成立，再看对应代码，而不是先背模板。

动画 6 · 代码映射

队列、分钟与 fresh 对应到 Go 语义行

重点观察扫描、冻结 size、感染入队、提前停止和最终失败判断。

Step 1/60%

时间 0 · 多源初始化

queue

(0,0)

queue=[(0,0)] · fresh=6

所有初始腐烂源同时入队

发生了什么: 扫描发现 c00=2，将坐标 (0,0) 入队；fresh 统计为 6。
为什么: 多源必须共享时间 0，不能让某个源先跑完整段传播。
下一步: 冻结当前队列长度 1，开始第 1 分钟。

当前状态

minutes

queue size

当前 Go 代码

1func orangesRotting(grid [][]int) int {2    rows, cols := len(grid), len(grid[0])3    queue := make([][2]int, 0)4    fresh := 05    for r := 0; r < rows; r++ { for c := 0; c < cols; c++ {6        if grid[r][c] == 2 { queue = append(queue, [2]int{r,c}) }7        if grid[r][c] == 1 { fresh++ }8    } }9    dirs := [][2]int{{1,0},{-1,0},{0,1},{0,-1}}10    minutes := 011    for fresh > 0 && len(queue) > 0 {12        size := len(queue)13        minutes++14        for i := 0; i < size; i++ {15            cell := queue[0]; queue = queue[1:]16            for _, d := range dirs { nr, nc := cell[0]+d[0], cell[1]+d[1]17                if nr<0 || nr>=rows || nc<0 || nc>=cols || grid[nr][nc]!=1 { continue }18                grid[nr][nc] = 219                fresh--20                queue = append(queue, [2]int{nr,nc})21            } }22    }23    if fresh > 0 {24        return -125    }26    return minutes27}

看完带走：每次状态变化都在入队时同步完成：改为 2、fresh--、加入下一层。

Step 1

先读懂 0、1、2

只有值为 1 的四邻格能发生状态变化，空格会阻断传播。

func · scan-grid

Step 2

所有初始腐烂源同时入队

多源必须共享时间 0，不能让某个源先跑完整段传播。

scan-grid · enqueue-source · count-fresh

Step 3

第 1 分钟：腐烂两个四邻格

这两个橘子是在第 1 分钟末才腐烂，不能在当前冻结层继续扩散。

while · freeze-size · minute-plus · visit-neighbor · rot-neighbor

Step 4

第 2 分钟：两个前沿同时工作

同层节点的处理先后不改变分钟，它们都携带相同的时间 1。

freeze-size · visit-neighbor · skip-invalid · rot-neighbor

Step 5

第 3 分钟：空格挡住错误方向

边界外、空格和已腐烂格都不是新鲜邻居，必须跳过。

visit-neighbor · skip-invalid · rot-neighbor

Step 6

第 4 分钟：最后一个新鲜橘子腐烂

每次感染立即扣减 fresh，能精确知道全部目标何时完成。

minute-plus · rot-neighbor · fresh-minus · enqueue-rotten

Step 7

完成时立即停在答案 4

若只按 queue 非空继续循环，会处理最后一个腐烂格并把时间错误加到 5。

while · fresh-check · return-minutes

Step 8

队列耗尽仍有 fresh，说明不可达

所有可达前沿都已经处理，不可能再产生新的腐烂橘子。

fresh-check · return-failure

Step 9

每个格子最多入队一次

因此总工作量和最坏队列容量都与格子数量 m×n 成正比。

scan-grid · while · return-minutes

10交互算法精讲

完整 Go 提交代码与最小测试

完整 Go 解法

1func orangesRotting(grid [][]int) int {2    rows, cols := len(grid), len(grid[0])3    queue := make([][2]int, 0)4    fresh := 05    for r := 0; r < rows; r++ { for c := 0; c < cols; c++ {6        if grid[r][c] == 2 { queue = append(queue, [2]int{r,c}) }7        if grid[r][c] == 1 { fresh++ }8    } }9    dirs := [][2]int{{1,0},{-1,0},{0,1},{0,-1}}10    minutes := 011    for fresh > 0 && len(queue) > 0 {12        size := len(queue)13        minutes++14        for i := 0; i < size; i++ {15            cell := queue[0]; queue = queue[1:]16            for _, d := range dirs { nr, nc := cell[0]+d[0], cell[1]+d[1]17                if nr<0 || nr>=rows || nc<0 || nc>=cols || grid[nr][nc]!=1 { continue }18                grid[nr][nc] = 219                fresh--20                queue = append(queue, [2]int{nr,nc})21            } }22    }23    if fresh > 0 {24        return -125    }26    return minutes27}

最小测试集合

// 主例：四轮全部腐烂
orangesRotting([][]int{{2,1,1},{1,1,0},{0,1,1}}) // 4

// 初始没有新鲜橘子，不需要等待
orangesRotting([][]int{{0,2}}) // 0

// 存在不可达的新鲜橘子
orangesRotting([][]int{{2,1,1},{0,1,1},{1,0,1}}) // -1

// 多个初始源必须同时传播
orangesRotting([][]int{{2,1,2},{1,1,1}}) // 2

11交互算法精讲

正确性与复杂度

时间复杂度 O(mn)

初始化扫描 m×n 个格子，每个新鲜格最多被感染并入队一次。

空间复杂度 O(mn)

最坏情况下队列可以同时保存与网格格子数同阶的传播前沿。

12交互算法精讲

最容易写错的地方

错误 1

只把一个初始腐烂源入队。

错误 2

每弹出一个橘子就让 minutes++。

错误 3

入队时不立即改为 2，导致重复入队。

错误 4

忘记传播结束后检查 fresh，或把初始 fresh=0 算成 1 分钟。

13交互算法精讲

最后复盘：带走逻辑链

1.多源 BFS = 所有源共享同一个时间 0。
2.冻结队列长度 = 固定当前一分钟的传播前沿。
3.fresh 既帮助提前停止，也负责判断不可达。
4.迁移题：LC542 01 矩阵、LC1091 网格最短路。

面试表达

1.这是多源 BFS：先把所有初始腐烂橘子入队，同时统计 fresh。
2.每轮冻结队列长度，处理这一层的四方向新鲜邻居，感染时立即标记并 fresh--。
3.一层代表一分钟；结束后 fresh>0 返回 -1，否则返回分钟数。
4.每格最多处理一次，时间 O(mn)，最坏队列空间 O(mn)。