LeetCode 994：腐烂的橘子——Java 多源 BFS 分层扩散详解

一、题目描述给定一个m × n的网格grid其中0表示空单元格1表示新鲜橘子2表示腐烂橘子。每经过一分钟腐烂橘子会使其上、下、左、右四个方向相邻的新鲜橘子腐烂。要求返回所有新鲜橘子全部腐烂所需的最少分钟数如果存在永远无法腐烂的橘子则返回-1。例如grid [[2,1,1], [1,1,0], [0,1,1]]最终所有橘子都会腐烂最少需要4分钟。二、核心思路多源 BFS这道题本质上是一个网格中的分层扩散问题。普通 BFS 通常只有一个起点而网格中可能同时存在多个腐烂橘子。它们在第 0 分钟会一起开始扩散因此必须先把所有初始腐烂橘子放入队列让它们作为多个起点同时进行 BFS这就是多源 BFS。整体分为三步遍历网格统计新鲜橘子数量fresh将所有初始腐烂橘子的位置加入队列按分钟分层处理队列使相邻的新鲜橘子腐烂。每一轮处理的都是“上一分钟已经腐烂的橘子”它们在这一分钟共同向四周扩散。因此一轮 BFS 就对应一分钟。三、为什么要统计新鲜橘子数量只记录扩散时间还不够因为有些新鲜橘子可能被空格隔开始终无法接触到腐烂橘子。初始化时统计新鲜橘子的总数fresh。每当一个新鲜橘子被腐烂就执行fresh--;BFS 结束后有两种情况fresh 0所有新鲜橘子都已腐烂返回经过的分钟数fresh 0仍有橘子无法被扩散到返回-1。这种方式既能判断任务是否完成也不需要在 BFS 结束后再次扫描整个网格。四、分层扩散过程以示例一为例2 1 1 1 1 0 0 1 1第 0 分钟队列中只有初始腐烂橘子(0,0)。第 1 分钟它使(0,1)、(1,0)腐烂第 2 分钟这两个橘子继续扩散使(0,2)、(1,1)腐烂第 3 分钟(1,1)使(2,1)腐烂第 4 分钟(2,1)使(2,2)腐烂。此时fresh变成 0因此答案为 4。关键点在于同一分钟内刚腐烂的橘子应当等到下一轮才能继续扩散。代码中可以使用一个新列表保存下一分钟的腐烂橘子从而自然划分层次。五、为什么发现新鲜橘子后要立即标记当某个新鲜橘子第一次被访问时要立即把它从1修改为2然后再加入下一层队列grid[nextRow][nextCol] 2; nextLevel.add(new int[]{nextRow, nextCol});不能等到它出队时再修改。因为同一个新鲜橘子可能同时与多个腐烂橘子相邻如果不立即标记它会被重复加入队列导致fresh被多次减少甚至造成错误结果。这里的原地修改同时承担了visited数组的作用grid[i][j] 1尚未腐烂可以访问grid[i][j] 2已经腐烂或已经加入队列不再重复处理。六、Java 代码实现import java.util.ArrayList; import java.util.List; class Solution { private static final int[][] DIRECTIONS { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; public int orangesRotting(int[][] grid) { int m grid.length; int n grid[0].length; int fresh 0; Listint[] rottenList new ArrayList(); // 统计新鲜橘子并收集所有初始腐烂橘子 for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { fresh; } else if (grid[i][j] 2) { rottenList.add(new int[]{i, j}); } } } int minutes 0; // 每轮循环表示经过一分钟 while (fresh 0 !rottenList.isEmpty()) { minutes; Listint[] currentLevel rottenList; rottenList new ArrayList(); for (int[] position : currentLevel) { for (int[] direction : DIRECTIONS) { int nextRow position[0] direction[0]; int nextCol position[1] direction[1]; if (nextRow 0 nextRow m nextCol 0 nextCol n grid[nextRow][nextCol] 1) { fresh--; grid[nextRow][nextCol] 2; rottenList.add(new int[]{nextRow, nextCol}); } } } } return fresh 0 ? -1 : minutes; } }七、代码关键点1. 为什么循环条件是fresh 0 !rottenList.isEmpty()只要新鲜橘子已经全部消失就不需要继续扩散如果队列已经为空说明没有新的腐烂橘子能够继续影响周围即使仍有新鲜橘子也只能退出并返回-1。2. 为什么先执行minutes进入一轮循环表示当前这一批腐烂橘子将向外扩散一次也就是经过了一分钟。循环结束后新产生的腐烂橘子会在下一轮继续扩散。3. 没有新鲜橘子时为什么返回 0如果初始网格中fresh 0循环根本不会执行minutes保持为 0正好符合题意。八、复杂度分析设网格共有m × n个单元格。时间复杂度O(mn)。每个单元格最多被扫描和入队一次空间复杂度O(mn)。最坏情况下队列需要保存大量橘子的位置。九、常见错误第一只把一个腐烂橘子加入队列。题目中的所有初始腐烂橘子会同时扩散必须全部作为 BFS 起点。第二使用 DFS 递归扩散。DFS 可以判断能否到达却不方便保证得到最少分钟数BFS 的层数天然对应最短扩散时间。第三加入队列后不立即修改网格。这会导致同一个橘子被重复加入队列。第四只返回 BFS 层数不检查剩余新鲜橘子。被隔离的橘子无法腐烂此时必须返回-1。十、总结“腐烂的橘子”是典型的多源 BFS 问题。所有初始腐烂橘子共同构成第 0 层之后每扩散一层就代表经过一分钟。代码中使用fresh记录剩余新鲜橘子并在橘子入队时立即将其标记为腐烂既能避免重复访问也能在结束时判断是否存在无法腐烂的橘子。面试时可以概括为先将所有腐烂橘子作为多源起点加入队列再按层进行 BFS每层表示一分钟扩散时减少新鲜橘子数量最后若仍有新鲜橘子则返回-1否则返回 BFS 层数。