本题采用多源广度优先搜索Multi-Source BFS层序图遍历算法解决网格状态传播与最短时间计算问题。其核心本质是将所有初始腐烂橘子视为并行的图节点源头以分钟为单位向四周进行同步拓扑扩散利用新鲜橘子计数器的实时递减来精确控制传染终点。当前提供的源码实现了在时间复杂度 O(m * n) 和额外空间复杂度 O(m * n) 条件下的多源洪泛扩散最终走向是精准输出所有橘子全部腐烂所需的最短时间或者在存在孤立点时判定不可能完成。一、 问题本质与数据模型对于大小为 m x n 的二维网格矩阵 grid题目引入了动态时间维度上的状态机状态演进状态流转约束单元格数值 2腐烂在每一分钟会将四周相邻的 1新鲜同化为 2。数值 0空单元格充当物理阻隔阻断传播。同时多源爆发腐烂的传染并不是由单个点启动的而是全图上所有现存的数值 2 在同一时刻向外辐射。如果在解决该问题时采用常规的单源搜索或深度优先搜索DFS将会因为无法同步时间步调而导致“最短分钟数”的计算逻辑彻底失效DFS 会一路深入单条路径无法模拟多点并行的真实时间推进。为了破除时间步调不一致的拓扑困局算法引入了“多源层序洪泛模型”。在初始化阶段算法执行全盘线性扫描完成两件事一是统计全局新鲜橘子的总量fresh作为后续收敛的评判判据二是将所有初始腐烂橘子的坐标一次性注入集合pos中。此处的pos集合在物理上扮演了多源 BFS 初始队列的角色。随后的每一次while循环迭代都代表时间指针前推了 1 分钟。算法通过“双列表交替覆盖”的设计确保当前分钟内所有腐烂源产生的次生感染节点被打包放入下一轮次的容器中从而在网格空间内实现了绝对时间意义上的均等同步扩散。二、 算法演进对比在解决网格状态多源传播的最短路径时间问题时多源 BFS 是公认的理论最优解解法名称时间复杂度空间复杂度核心原理物理瓶颈 / 缺陷单源 BFS 穷举叠加O(k * m * n)O(m * n)对每个初始腐烂橘子单独跑一次 BFS最后取每个新鲜橘子被感染的最小值再取全局最大值存在大量重复的网格扫描与路径重叠计算性能随初始腐烂橘子数 k 的增加而线性退化动态规划DP/ 记忆化 DFSO(m * n)O(m * n)测算每个新鲜橘子到最近腐烂橘子的曼哈顿距离由于存在障碍物 0 阻断路径非简单的几何距离计算状态转移方程的物理装配极度繁琐多源 BFS当前解法O(m * n)O(m * n)所有腐烂源同时入队通过双列表交替模拟时间步进原地修改网格状态依赖额外的线性容器存储边界坐标但在时空平衡性与逻辑直观度上达到了极限三、 核心分支控制逻辑与决策证明当前源码的控制流完全依赖于外层双重循环初始化、while多源并发扩散以及四向边界防护网其内部决策分支证明如下1. 状态初始化与计数分支 (grid[i][j] 1或2)执行分别触发fresh和pos.add(...)。物理意义建立全局先验模型。fresh计数器的存在使算法能够在中途新鲜橘子清零时立刻提前终止并且在尾部提供 O(1) 的完备性校验无需二次遍历网格。2. 扩散循环控制核心while (!pos.isEmpty() fresh 0)执行双重条件控制。数学证明只有当队列中仍有“具备传染能力的腐烂源”且“全图仍有未被感染的新鲜橘子”时时间迭代才有意义。若fresh已归零即使队列不为空也必须拦截自增规避最后一层无效空跑导致时间多算 1 分钟。3. 双列表层级迭代Listint[] cur pos; pos new ArrayList();执行暂存当前层清空原引用指向新容器。数学证明这是对标准队列queue.size()逻辑的替代实现。通过将“当前分钟的传染源”与“下一分钟产生的新传染源”在物理内存上隔离开确保ans对应的是一整层节点的向外步进实现了图的层序拓扑演进。4. 四向边界与状态校验if (x 0 x grid.length ... grid[x][y] 1)执行fresh--grid[x][y] 2并将新坐标压入pos。数学证明边界判定消除了数组越界隐患。核心筛选条件grid[x][y] 1实现了精准剪枝空单元格0和已腐烂单元格2直接被无视只有原生新鲜橘子才会触发状态坍塌。原地改写为 2 保证了该节点在后续时间片中不会被重复感染。四、 算法执行状态机步进示例以输入矩阵grid [ [2, 1, 1], [1, 1, 0], [0, 1, 1] ]为例规模 3 x 3展示多源扩散状态机的演进全貌步骤当前时间计数 ans激活的当前传染源集合 cur被同化的新坐标及网格变化剩余新鲜橘子数 fresh下一轮次就绪的队列 pos初始0-扫描定位(0,0)为2新鲜橘子共 6 个6[ (0,0) ]11[ (0,0) ](0,0)向右同化(0,1)向下同化(1,0)4[ (0,1), (1,0) ]22[ (0,1), (1,0) ](0,1)向右同化(0,2)(1,0)向下遭遇0拦截向右同化(1,1)2[ (0,2), (1,1) ]33[ (0,2), (1,1) ](0,2)无有效邻居(1,1)向下同化(2,1)1[ (2,1) ]44[ (2,1) ](2,1)向右同化(2,2)此时 fresh 归零0[ (2,2) ]终止4-while 条件中fresh 0失效退出循环0最终出口返回ans 4五、 源码实现import java.util.ArrayList; import java.util.List; class Solution { public int orangesRotting(int[][] grid) { // 静态方向矩阵映射依次代表向右、向下、向左、向上四个物理移动偏移行程 int[][] dir new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 使用 List 集合模拟 BFS 队列存储当前层级的腐烂橘子物理坐标 Listint[] pos new ArrayList(); int ans 0; int fresh 0; // 全盘线性扫描建立初始化多源拓扑图并统计全局新鲜橘子基数 for (int i 0; i grid.length; i) { for (int j 0; j grid[0].length; j) { if (grid[i][j] 1) { fresh; // 新鲜橘子计数自增 } if (grid[i][j] 2) { pos.add(new int[]{i, j}); // 腐烂橘子坐标注入初始多源集合 } } } // 核心多源层序控制当前层不为空且仍有待拯救的新鲜橘子时状态机向前步进 while (!pos.isEmpty() fresh 0) { ans; // 时间指针推进 1 分钟 Listint[] cur pos; // 锁定当前分钟的全部活动传染源 pos new ArrayList(); // 物理开辟新容器用以装载下一分钟的次生感染源 // 迭代处理当前时间片内的每一个腐烂源 for (int[] curr : cur) { for (int[] d : dir) { int x curr[0] d[0]; int y curr[1] d[1]; // 四向安全边界防护网拦截越界坐标且目标格点必须为新鲜橘子1 if (x 0 x grid.length y 0 y grid[0].length grid[x][y] 1) { fresh--; // 全局未感染基数递减 grid[x][y] 2; // 原位篡改状态完成物理同化防止被重复访问 pos.add(new int[]{x, y}); // 将新传染源压入下一轮次的迭代序列中 } } } } // 完备性终审若退出图遍历后仍有新鲜橘子残留说明存在物理孤岛返回 -1否则返回累计分钟数 return (fresh 0) ? -1 : ans; } }六、 复杂度分析1. 时间复杂度O(m * n)分析算法首先执行了一次完整的双重嵌套循环扫描耗时与网格总面积 m * n 呈严格的正比关系。在后续的多源 BFS 洪泛扩散期间网格中的每个单元格最多只会被放入pos或cur容器中一次因为新鲜橘子一旦被触碰就会立即原地被篡改状态为 2不可逆转。在处理每个出队节点时对其上下左右四个方向的核验均属于常数阶操作 O(1)。结论算法总体基本操作的执行次数上限是网格总单元格数的常数倍时间复杂度为 O(m * n)达到了图遍历问题的最完美线性表现。2. 空间复杂度O(m * n)分析该解法直接对输入的grid矩阵执行原位状态改写因此在网格存储上表现为 O(1)。然而为了实现层序时间步进算法引入了pos和cur两个局部线性集合。在最坏情况下例如除了一个格子外全图在初始时全部为腐烂橘子或者传染在某一分钟全面爆发这两个集合中并存的节点坐标总量将逼近整个网格的规模 m * n。结论由于使用了非递归的迭代形式消除了系统方法栈的空间开销其额外空间的消耗完全由堆内存中的局部列表决定空间复杂度定性为 O(m * n)。