第8章｜图与并查集

Unit 05 · LeetCode #994 腐烂的橘子

仅本次页面有效

U05

Multi-source BFS + Time LayersCollect Sources → Freeze Layer → Spread → Count Minutes

一分钟不是处理一个橘子，
而是让当前整层同时传播一次。

普通 BFS 回答“能否到达”；本单元进一步回答“最少几分钟到达”。所有初始腐烂橘子必须在第 0 分钟同时进入队列，随后每一层对应同一个时间戳。

检测到上次学习现场阶段、案例、动画、问题、槽位、迁移脚手架、代码高度和滚动位置均可恢复。

给定 m × n 网格：0 表示空格，1 表示新鲜橘子，2 表示腐烂橘子。每分钟，腐烂橘子会使上下左右相邻的新鲜橘子腐烂。返回没有新鲜橘子所需的最少分钟数；无法完成时返回 -1。

示例 1 [[2,1,1], [1,1,0], [0,1,1]] 输出：4 示例 2 [[2,1,1], [0,1,1], [1,0,1]] 输出：-1 示例 3 [[0,2]] 输出：0

m == grid.length n == grid[i].length 1 ≤ m, n ≤ 10 grid[i][j] ∈ {0, 1, 2} class Solution: def orangesRotting(self, grid): ...

本实验采用“冻结当前层长度”的多源 BFS。只有传播完当前层后，分钟数才增加一次。

queue

当前分钟已经腐烂、将在这一分钟向外传播的橘子。新增腐烂节点进入下一层。

fresh

尚未腐烂的新鲜橘子数量。它同时承担完成条件与不可达检测。

minutes

已经完整执行的传播层数，而不是弹出节点的次数。

Multi-source BFS

多个初始源同时进入第 0 层，等价于从一个超级源点出发。

Layer Boundary

进入本轮前冻结 len(queue)，防止下一层节点提前传播。

First Arrival

无权图 BFS 第一次到达某格子的层数，就是它到最近源的最短距离。

Unreachable

队列已经为空但 fresh > 0，说明存在被空格阻断的新鲜橘子。

多源 BFS 实验步骤 1

多源最短传播 = 所有源同时入队 + 冻结层边界 + 首次发现即标记。当前层中的节点代表同一分钟；下一层节点的时间统一比当前层多一。队列耗尽后仍有新鲜橘子，说明它们对所有源都不可达。

Graph Model非空格子是节点，四方向相邻形成无权边

Sources所有初始腐烂橘子共同构成第 0 层

Frontier冻结 len(queue) 得到当前分钟边界

Visited发现新鲜橘子时立即改为 2

Finishfresh == 0 成功，否则队列空时返回 -1

Complexity时间 O(mn)，队列空间 O(mn)

完成后停留在当前页面

不会倒计时或自动跳题。可以返回任意阶段重播时间层，也可以继续修改迁移代码。