烂橘子蔓延 — 多源 BFS
Rotting Oranges — Multi-Source BFS
开始编码你在维护一个内部风险模型的故障蔓延模拟器:状态落在一张 R × C 网格上,每格取三种值之一:0(空格 / 没有资产)、1(健康节点,类比「新鲜橘子」)、2(已故障节点,类比「烂橘子」)。每过一分钟,所有与至少一个故障节点 4 邻接的健康节点也会失效——故障在所有「感染前线」上同步并行地推进。请你计算所有健康节点都失效所需的最少分钟数;如果存在某个健康节点永远无法被任何故障源到达,返回 -1。
请实现 solution(grid: list[list[int]]) -> int。三条规则:(1)第 0 分钟时所有值为 2 的格子已经故障;(2)此后每过一分钟,所有与某个值-2 格子 4 邻接的值-1 格子变成值 2;(3)答案是「使得网格中不再有值-1 格子」的最小 t,若某些值-1 格子永远变不了,返回 -1。两个重要边界:开局就没有值-1 格子时,答案是 0(目标已满足,不是 -1);有值-1 但没有值-2 时,答案是 -1(没有源就无从蔓延)。
示例 1:solution([[2,1,1],[1,1,0],[0,1,1]]) 返回 4。唯一源 (0,0) 在 t=1 感染 (0,1) 与 (1,0);t=2 感染 (0,2) 与 (1,1);t=3 感染 (2,1);t=4 感染 (2,2)——4 分钟全部腐烂。示例 2:solution([[2,1,1],[0,1,1],[1,0,1]]) 返回 -1:(2,0) 被 (1,0) 与 (2,1) 处的零完全围住,永远到不了。示例 3:solution([[0,2]]) 返回 0:网格里没有 fresh,目标已自动满足。
正确解法是网格上的多源 BFS:开局把所有烂橘子(带距离 0)一并塞进队列,再按 4 邻接展开。无权图 BFS 给出「到最近源」的最短距离,所以每个 fresh 第一次被访问时的距离就是它腐烂的那一分钟。答案是所有 fresh 被访问到的距离的最大值;BFS 跑完仍有 fresh 没被访问到则返回 -1。每个格子最多入队一次,时间复杂度 O(R·C)。这种「系统某些部分先失效,沿连通图并行级联」的形态在量化基础设施里随处可见——切片化行情缓存里的同步 tile 失效广播、跨保证金组合中的爆仓级联、对手方敞口图上的违约传染——所求的「分钟数」就是「从任意源到任意尚未失效节点」的最长传播路径。
约束条件
- 1 ≤ R, C ≤ 50(网格尺寸)
- grid[i][j] ∈ {0, 1, 2},其中 0 = 空格子,1 = 新鲜橘子,2 = 烂橘子
- 蔓延方向为 4 邻接(上下左右;不包括对角线)
- 所有烂橘子在第 0 分钟同时开始蔓延
- 若初始就没有新鲜橘子,返回 0(已合格)
- 若至少有一个新鲜橘子永远无法被任何烂橘子感染,返回 -1
样例
Case 1 · leetcode 994 sample — typical multi-step propagation
输入: [[[2,1,1],[1,1,0],[0,1,1]]]
期望: 4
起点是 (0,0) 的烂橘子。第 1 分钟感染 (0,1) 和 (1,0);第 2 分钟感染 (0,2) 和 (1,1);第 3 分钟感染 (2,1);第 4 分钟感染 (2,2)。所有 fresh 都已烂掉,最少耗时 4 分钟。
Case 2 · isolated fresh — infeasible
输入: [[[2,1,1],[0,1,1],[1,0,1]]]
期望: -1
(2,0) 上方是 (1,0)=0,下方越界,右边是 (2,1)=0,被零完全包住,烂源永远到不了它。所以返回 -1。
Case 3 · no fresh, only rotten and empty — zero minutes
输入: [[[0,2]]]
期望: 0
没有 fresh 橘子,无需等待,返回 0。这是「初始状态已合格」的边界情形。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
Case 1 · leetcode 994 sample — typical multi-step propagation
输入: [[[2,1,1],[1,1,0],[0,1,1]]]
期望: 4
起点是 (0,0) 的烂橘子。第 1 分钟感染 (0,1) 和 (1,0);第 2 分钟感染 (0,2) 和 (1,1);第 3 分钟感染 (2,1);第 4 分钟感染 (2,2)。所有 fresh 都已烂掉,最少耗时 4 分钟。
Case 2 · isolated fresh — infeasible
输入: [[[2,1,1],[0,1,1],[1,0,1]]]
期望: -1
(2,0) 上方是 (1,0)=0,下方越界,右边是 (2,1)=0,被零完全包住,烂源永远到不了它。所以返回 -1。
Case 3 · no fresh, only rotten and empty — zero minutes
输入: [[[0,2]]]
期望: 0
没有 fresh 橘子,无需等待,返回 0。这是「初始状态已合格」的边界情形。