最近刷力扣热题100做到第994题“腐烂的橘子”时我停下来多看了几眼。这道题在力扣上标记为中等难度但它在面试里出现的频率相当高因为它在同一道题里集中考察了图论建模、多源BFS思想、队列的层级遍历、以及边界条件的处理几乎每一条都是算法面试的高频考点。很多刷题攻略里把它放在“搜索”专题的开篇位置是有道理的。我第一次做这道题时以为很简单但真正跑起来才发现坑不少。比如分钟数怎么计才准确多个烂橘子同时扩散时队列怎么初始化最后如何判断新鲜橘子永远烂不掉的情形……这些细节如果只看题解很容易一带而过但实际动手写代码时每一步都可能有偏差。这篇文章把我的完整思路、实现过程、以及踩过的几个坑都整理出来希望能帮到正在按顺序刷力扣的朋友们。1. 题意拆解别小看这道题它考的是多源BFS建模1.1 题目到底在说什么力扣994的题干说得比较直白一个m x n的网格每个格子有三种状态0代表空1代表新鲜橘子2代表腐烂橘子。每分钟腐烂橘子会把它上下左右四个方向相邻的新鲜橘子也感染成腐烂的。要求返回网格里所有新鲜橘子全部腐烂所需的最小分钟数如果存在永远无法被感染的新鲜橘子则返回-1。这个描述本质上是一个离散时间步的传播过程。我之所以说它考察图论建模是因为网格本身就是一张隐式的图每个格子是一个节点上下左右相邻的格子之间存在边。感染传播的过程就是从初始的腐烂橘子出发逐层向外扩散的过程。题目里有个容易被忽略的关键点“每分钟”意味着所有腐烂橘子是同步扩散的。换句话说第1分钟所有初始腐烂橘子同时感染各自的邻居第2分钟这些新被感染的橘子再同时感染它们的邻居。这种同步性让这个问题天然适合用BFS的层序遍历来建模。1.2 简单题的外表下隐藏的三个考点我第一次做完这道题之后复盘发现它其实藏了三个独立的考点。第一个考点是初始状态的处理。题目没有保证网格里一定存在腐烂橘子。如果全是新鲜橘子那答案是-1因为没有源头可以传播如果全是空格子而没有橘子答案是0。这个边界如果不处理后面逻辑很容易出错。第二个考点是层数与分钟数的对应关系。BFS天然按层遍历每一层就是对应用一分钟的传播。但怎么把“层数”和“分钟数”对应起来很多新手会在这里翻车——不是多算一分钟就是少算一分钟。第三个考点是最坏情况的判断。如果某些新鲜橘子被空格隔开永远接触不到腐烂源题目要求返回-1。这要求遍历结束后还要再扫一遍网格检查是否还有新鲜橘子残留。这三个考点组合在一起就决定了这道题必须用多源BFS而不是简单的单源搜索。1.3 为什么多源BFS是这道题的题眼传统的BFS从单个起点出发求这个起点到所有其他点的最短距离。而这道题的初始状态可能有多个腐烂橘子它们在同一时刻开始扩散所以等价于把多个源点同时放入队列一起开始BFS。我第一次想到这个问题时第一反应是能不能分别对每个烂橘子做一次BFS然后取重叠区域的最小值。但这个思路在逻辑上就有问题腐烂是同时传播的而不是分开传播的。如果分别算两个源点之间的新鲜橘子会被重复计算路径交叉也会处理不干净。更致命的是完全分开的传播区域之间无法模拟“扩散相遇”的情况。所以正确答案只有一个初始化时把所有腐烂橘子一次性加入队列然后统一进行BFS。这就是多源BFS。理解了这一点整道题的骨架就搭好了。2. 暴力模拟为什么不可取我先写了一个容易理解的版本然后发现它太慢了2.1 最直观的迭代扫描思路做题时我习惯先从一个最朴素、最“笨”的版本入手。这道题最朴素的思路是这样每一分钟都遍历整个网格把所有当前还是新鲜橘子、并且上下左右存在腐烂橘子的格子标记为新的腐烂橘子一分钟结束后更新网格状态重复这个过程直到某一分钟没有任何新的橘子被感染或者所有新鲜橘子都烂完了。这个思路能够正确运行代码写起来也直接我在本地测试时很快就跑通了。但它有一个问题每一分钟都要扫描一次全表需要的时间是O(k × m × n)其中k是总共模拟的分钟数。如果网格是50x50最坏情况下需要几十步勉强还能接受但如果网格是1000x1000k也可能达到几千这个复杂度就非常尴尬了。2.2 时间复杂度让人头疼我具体估算了一下。假设网格大小是n × m腐烂橘子在最角落新鲜橘子在最远的对角那么至少需要n m分钟才能全部感染完。每分钟扫描n × m个格子总复杂度是O((n m) × n × m)。这样的复杂度在数据范围较大时会接近甚至超过一亿次操作在力扣上基本会超时。所以这个思路只能作为理解题意的辅助不适合作为正式提交的解法。2.3 从暴力模拟到BFS的思维转变既然逐分钟模拟的问题在于反复扫描全表那有没有办法只处理“边界”上的格子呢这里就是BFS的切入点。BFS之所以高效是因为每个格子最多入队一次、出队一次访问的总次数是O(n × m)而不是“分钟数 × 格子数”。处理一分钟的传播等价于BFS中处理队列的当前一层处理完这一层再进入下一层。整个搜索一遍完成所有橘子被感染的时间顺序就天然排好了。我个人的体会是从暴力扫描到BFS的转变核心是把思维模式从“全局扫描”切换成“事件驱动”。每一分钟真正需要处理的只是上一轮刚被感染的那些橘子而不是全网格所有格子。队列天然支撑了这个需求新感染的橘子入队下一轮从队列中取出它们再扩散。有了这个认知后面的实现就顺理成章了。3. 多源BFS的完整实现Python和Java双版本逐行解读3.1 整体算法流程实现多源BFS之前先把整体流程写清楚。我分成四步遍历整个网格把所有值为2的格子加入队列同时统计新鲜橘子的数量。用变量记录当前BFS的层数或者说分钟数。进入BFS循环每次处理完当前队列中的所有节点才算过了一分钟。BFS结束后扫描一遍网格如果还有值为1的格子说明有新鲜橘子无法被感染返回-1否则返回分钟数。步骤1里的存在性判断可以提前做如果最初就没有新鲜橘子直接返回0。如果没有腐烂橘子但有新鲜橘子直接返回-1。3.2 Python版本的代码与注释from collections import deque class Solution: def orangesRotting(self, grid: List[List[int]]) - int: rows, cols len(grid), len(grid[0]) queue deque() fresh 0 # 初始化把所有腐烂橘子入队统计新鲜橘子数 for i in range(rows): for j in range(cols): if grid[i][j] 2: queue.append((i, j)) elif grid[i][j] 1: fresh 1 # 如果没有新鲜橘子直接返回0 if fresh 0: return 0 minutes 0 directions [(-1, 0), (1, 0), (0, -1), (0, 1)] while queue and fresh 0: minutes 1 size len(queue) for _ in range(size): x, y queue.popleft() for dx, dy in directions: nx, ny x dx, y dy if 0 nx rows and 0 ny cols and grid[nx][ny] 1: grid[nx][ny] 2 queue.append((nx, ny)) fresh - 1 return minutes if fresh 0 else -1这段代码里最关键的地方有两个。第一个是用 size 记录当前层的节点数因为只有处理完当前层的所有节点才代表这一分钟结束。第二个是循环条件中加了 fresh 0一旦新鲜橘子数量归零就可以提前退出不必再继续处理队列里剩余的节点。提示在 while 循环开头执行 minutes 1而不是在处理完一层之后再加这样可以避免“最后几分钟的额外1”问题。我一开始写成处理完一层再加结果答案总是比预期大1。3.3 Java版本与Python版本的关键差异Java版本的核心逻辑完全一致但因为Java没有Python那么方便的元组和解构代码里的样板代码会更长一些。这里我给出一个干净、可读性优先的版本。class Solution { public int orangesRotting(int[][] grid) { int rows grid.length, cols grid[0].length; Queueint[] queue new LinkedList(); int fresh 0; for (int i 0; i rows; i) { for (int j 0; j cols; j) { if (grid[i][j] 2) { queue.offer(new int[]{i, j}); } else if (grid[i][j] 1) { fresh; } } } if (fresh 0) return 0; int minutes 0; int[][] dirs {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; while (!queue.isEmpty() fresh 0) { minutes; int size queue.size(); for (int i 0; i size; i) { int[] cell queue.poll(); for (int[] d : dirs) { int nx cell[0] d[0], ny cell[1] d[1]; if (nx 0 nx rows ny 0 ny cols grid[nx][ny] 1) { grid[nx][ny] 2; queue.offer(new int[]{nx, ny}); fresh--; } } } } return fresh 0 ? minutes : -1; } }Java版需要注意的一点是Queueint[] 里的数组元素是引用类型poll出来之后可以直接修改不会影响队列里的其他元素因为数组只被当前变量引用一次没有共用风险。这一点在刷题时不会出问题但如果把同一个数组引用加入多个结果集就要小心了。3.4 另一种实现思路直接在格子上记录感染时间除了用队列分层计数还有一种常见的实现方式不用 minutes 变量而是把每个格子被感染的时间直接写到 grid 数组里。初始腐烂橘子对应时间0每次感染新橘子时把 grid[nx][ny] 设为 grid[x][y] 1。BFS结束后扫描整个网格找到最大的时间值就是答案如果还有新鲜橘子则返回-1。这种方式的好处是直观调试时能直接看到每个格子上的“腐烂时间”。我在本地测试时用过这个版本打印网格状态非常方便。缺点是会修改原始数组的语义把1、2、0这些状态位覆盖成时间值所以如果想在函数结束后继续用原数组需要先复制一份。以 Python 为例这个版本可以写成def orangesRotting_timeVersion(self, grid): rows, cols len(grid), len(grid[0]) queue deque() fresh 0 for i in range(rows): for j in range(cols): if grid[i][j] 2: queue.append((i, j)) elif grid[i][j] 1: fresh 1 if fresh 0: return 0 dirs [(-1, 0), (1, 0), (0, -1), (0, 1)] max_time 0 while queue: x, y queue.popleft() for dx, dy in dirs: nx, ny x dx, y dy if 0 nx rows and 0 ny cols and grid[nx][ny] 1: grid[nx][ny] grid[x][y] 1 fresh - 1 queue.append((nx, ny)) max_time max(max_time, grid[nx][ny]) return max_time if fresh 0 else -1这个版本不需要 size 变量因为时间信息直接存在坐标里。它的缺点是在初始化时没有把 max_time 设为0的特殊情况处理所以需要在一开始就排除掉 fresh 0 的情况。整体来说两个版本的时间复杂度相同选择哪个取决于个人习惯。4. 我实际踩过的坑分钟计数、边界检查与DFS的误区4.1 分钟数比预期大1的问题我第一次提交时用了一个“处理完一层再加分钟数”的逻辑结果在测试样例上总是比预期答案大1。为什么因为BFS的层数和传播分钟数之间有一层微妙的偏移关系。假设初始腐烂橘子在第0分钟就已经存在。队列初始包含这些腐烂橘子它们对应的时间是0。如果我在处理完这一层也就是没有任何新感染发生之后才 minutes 1那么最后一次传播结束后的额外加1就是多余的。以只有一个烂橘子、周围有1个新鲜橘子的最简单情况为例第1分钟腐烂橘子感染新鲜橘子。如果我的循环是“先取出一层处理完感染后 minutes 1”那第1分钟的处理会先让新鲜橘子变腐烂然后此刻 minutes 才变成1。看上去好像没问题但如果队列里还有后续节点或者处理过程中 new_fresh 被减到0但循环没有立刻退出就会多算一个分钟。解决方式有几个我选择的是在 while 循环开头直接 minutes 1这样每处理一层就对应一分钟不会多算。如果新感染数在某一轮为0说明这分钟没有任何传播发生循环条件 fresh 0 也会提前退出不会有多余计数。4.2 边界检查少写一个方向方向数组四个方向的写法非常固定上下左右是 (dx, dy) 分别为 (-1,0), (1,0), (0,-1), (0,1)。我一开始写的是三个方向漏掉了向左这一项导致部分区域永远不会被感染测试用例里有一个 [[2,1,1],[1,1,0],[0,1,1]] 的样例答案本应是4我输出的是5甚至更大的数因为左边的橘子一直烂不过来。这类错误写代码时很容易犯因为它不会直接报错只是结果不对。我总结的检查方法是在本地用一组自己手算过的数据去验证比如一个4x4网格手动列一分钟一分钟的传播表然后用代码跑一遍对比输出。如果答案不一致先print队列状态和每个格子的感染时间定位是哪一步的扩散路径出了问题。4.3 用DFS解这道题为什么容易出问题有一个很常见的误区是看到网格上的传播问题就想用DFS。DFS天然适合“是否存在路径”或“连通块大小”这类问题但腐烂橘子要求的是“最早全部感染的时间”也就是最短传播距离。用DFS做最短路径时虽然可以通过记录每个节点的时间值来实现但存在两个问题。第一个问题是DFS会深度优先走一条路走到黑可能先给某个格子赋了一个较大的时间值但后续另一条路径可以更早到达这个格子就需要回溯更新。这就退化成带备忘录的DFS复杂度很难保证。第二个问题是传染是同步发生的。DFS隐含的顺序性会导致“时间”的语义不准确。我在力扣讨论区看到过有人用DFS提交后得到超时或错误结果原因都是这两个。所以这道题的正确姿势就是BFS不要去和DFS较劲。4.4 初始状态为空的边界条件还有一个容易忽略的点是如果网格里根本没有新鲜橘子答案应该是0而不是某个负数或正值。我第一次写的时候没有处理 fresh 0 的情况导致结果是0的测试用例直接报错。同样如果网格里只有新鲜橘子而没有腐烂橘子答案应该是-1因为没有任何源点。这时候如果直接启动 BFS队列为空循环直接退出然后检查 fresh ! 0 就会返回-1逻辑上是自洽的。但为了可读性我建议在一开始就显式处理这两个边界而不是依赖后面的判断。注意力扣的测试用例里包含了很多极端情况比如1x1的网格只有 [[0]]或者只有 [[2]]。这类用例看起来简单但最容易暴露边界条件处理不到位的问题。5. 一题吃透一类题腐烂橘子的题型扩展与同类问题对比5.1 同一道题在面试中的变形腐烂橘子这道题在面试里很少被原封不动地提问更常见的是在它的基础上变换条件。我遇到过或听说过几种变形把“腐烂橘子”换成“病毒传播”本质不变只是把网格状态机换成新的语义。把“上下左右”四个方向换成“八连通”加上对角线改动只有方向数组。把“每分钟传播一次”改成“每轮随机若干次”那就不是BFS能解决的需要模拟。把问题改成“求最快全部感染的源点的个数”之类的优化问题那就升级成了更复杂的数学问题。面试时如果遇到这些变形先稳住核心还是多源BFS。方向数组改了初始源点变了但队列分层遍历的骨架完全一致。5.2 同类网格BFS题目我按照刷题经验整理了几道与腐烂橘子高度同源、可以一起刷的题目方便横向对比。题目难度与腐烂橘子的关系力扣200 岛屿数量中等网格连通块问题但用DFS更直观力扣542 01矩阵中等同样是多源BFS求每个0/1到最近目标的最短距离力扣1162 地图分析中等多源BFS求离陆地的最大海上距离力扣286 墙与门中等会员题多源BFS从门出发求房间距离力扣417 太平洋大西洋水流中等反向BFS从边缘出发向内搜索这些题的共同点是网格是图目标是距离搜索方式是BFS。差别主要在源点是单数还是复数、距离是曼哈顿距离还是自定义距离、搜索方向是从中心向外还是从外向内。5.3 刷了防腐橘子之后我对BFS有了什么新理解做这道题之前我对BFS的理解停留在“从单个源点出发求最短路径”的教科书层面。做完这道题我才真正理解了“多源”“层序”这两个概念在实际问题里是如何协同工作的。层序的意义在于它能精确地刻画“时间步”这一概念。在腐烂橘子问题里层与层之间恰恰对应一个分钟间隔。这种对应关系在很多现实问题里都存在比如社交网络的信息传播、城市交通的拥堵扩散、以及游戏里的感染机制。多源的意义在于多个起点可以同时出发而不需要分成多次搜索来模拟并行扩散。这让我在后面的刷题中养成了一个习惯拿到一道搜索题先问两个问题一是有几个起点二是搜索的目标是距离还是可达性。根据这两个问题的答案基本就能确定是用BFS还是DFS以及是否需要多源。5.4 一道好题的刷法建议最后说说我个人的刷题建议。像腐烂橘子这种一道题承载多个考点的题目我建议不要只追求提交通过就结束而是分三轮来刷。第一轮先按自己思路写一版哪怕超时也要写出来目的是理解题意。第二轮直接写正式版BFS要点是能解释清楚为什么多源、为什么分层、如何避免分钟1的坑。第三轮试着不看书本实现用不同的方式来写比如用记录时间值的版本或Java版本然后比较它们在边界条件处理上的差异。三轮下来这道题背后的思想就内化了。之后遇到 01矩阵、地图分析这类同类题基本可以十分钟内写出正确代码。这也是我推荐把这题纳入热题100的原因——它值得。我在实际刷题中的一个小习惯是每次做完一道题都会在本地建一个最小测试集手动标出每一个预期输出。然后再把代码跑一遍建立一个“先本地验证、再提交力扣”的固定流程。对于腐烂橘子这道题我已经积累了近十个边界样例包括空网格、全腐烂网格、有橘子但在另一块隔离区域的情况。这些样例不只是为了这一题后面刷同类题时也在反复复用。一步一个脚印地积累自己的调试数据库比反复看题解有用得多。
力扣994腐烂的橘子：多源BFS建模与实现详解
最近刷力扣热题100做到第994题“腐烂的橘子”时我停下来多看了几眼。这道题在力扣上标记为中等难度但它在面试里出现的频率相当高因为它在同一道题里集中考察了图论建模、多源BFS思想、队列的层级遍历、以及边界条件的处理几乎每一条都是算法面试的高频考点。很多刷题攻略里把它放在“搜索”专题的开篇位置是有道理的。我第一次做这道题时以为很简单但真正跑起来才发现坑不少。比如分钟数怎么计才准确多个烂橘子同时扩散时队列怎么初始化最后如何判断新鲜橘子永远烂不掉的情形……这些细节如果只看题解很容易一带而过但实际动手写代码时每一步都可能有偏差。这篇文章把我的完整思路、实现过程、以及踩过的几个坑都整理出来希望能帮到正在按顺序刷力扣的朋友们。1. 题意拆解别小看这道题它考的是多源BFS建模1.1 题目到底在说什么力扣994的题干说得比较直白一个m x n的网格每个格子有三种状态0代表空1代表新鲜橘子2代表腐烂橘子。每分钟腐烂橘子会把它上下左右四个方向相邻的新鲜橘子也感染成腐烂的。要求返回网格里所有新鲜橘子全部腐烂所需的最小分钟数如果存在永远无法被感染的新鲜橘子则返回-1。这个描述本质上是一个离散时间步的传播过程。我之所以说它考察图论建模是因为网格本身就是一张隐式的图每个格子是一个节点上下左右相邻的格子之间存在边。感染传播的过程就是从初始的腐烂橘子出发逐层向外扩散的过程。题目里有个容易被忽略的关键点“每分钟”意味着所有腐烂橘子是同步扩散的。换句话说第1分钟所有初始腐烂橘子同时感染各自的邻居第2分钟这些新被感染的橘子再同时感染它们的邻居。这种同步性让这个问题天然适合用BFS的层序遍历来建模。1.2 简单题的外表下隐藏的三个考点我第一次做完这道题之后复盘发现它其实藏了三个独立的考点。第一个考点是初始状态的处理。题目没有保证网格里一定存在腐烂橘子。如果全是新鲜橘子那答案是-1因为没有源头可以传播如果全是空格子而没有橘子答案是0。这个边界如果不处理后面逻辑很容易出错。第二个考点是层数与分钟数的对应关系。BFS天然按层遍历每一层就是对应用一分钟的传播。但怎么把“层数”和“分钟数”对应起来很多新手会在这里翻车——不是多算一分钟就是少算一分钟。第三个考点是最坏情况的判断。如果某些新鲜橘子被空格隔开永远接触不到腐烂源题目要求返回-1。这要求遍历结束后还要再扫一遍网格检查是否还有新鲜橘子残留。这三个考点组合在一起就决定了这道题必须用多源BFS而不是简单的单源搜索。1.3 为什么多源BFS是这道题的题眼传统的BFS从单个起点出发求这个起点到所有其他点的最短距离。而这道题的初始状态可能有多个腐烂橘子它们在同一时刻开始扩散所以等价于把多个源点同时放入队列一起开始BFS。我第一次想到这个问题时第一反应是能不能分别对每个烂橘子做一次BFS然后取重叠区域的最小值。但这个思路在逻辑上就有问题腐烂是同时传播的而不是分开传播的。如果分别算两个源点之间的新鲜橘子会被重复计算路径交叉也会处理不干净。更致命的是完全分开的传播区域之间无法模拟“扩散相遇”的情况。所以正确答案只有一个初始化时把所有腐烂橘子一次性加入队列然后统一进行BFS。这就是多源BFS。理解了这一点整道题的骨架就搭好了。2. 暴力模拟为什么不可取我先写了一个容易理解的版本然后发现它太慢了2.1 最直观的迭代扫描思路做题时我习惯先从一个最朴素、最“笨”的版本入手。这道题最朴素的思路是这样每一分钟都遍历整个网格把所有当前还是新鲜橘子、并且上下左右存在腐烂橘子的格子标记为新的腐烂橘子一分钟结束后更新网格状态重复这个过程直到某一分钟没有任何新的橘子被感染或者所有新鲜橘子都烂完了。这个思路能够正确运行代码写起来也直接我在本地测试时很快就跑通了。但它有一个问题每一分钟都要扫描一次全表需要的时间是O(k × m × n)其中k是总共模拟的分钟数。如果网格是50x50最坏情况下需要几十步勉强还能接受但如果网格是1000x1000k也可能达到几千这个复杂度就非常尴尬了。2.2 时间复杂度让人头疼我具体估算了一下。假设网格大小是n × m腐烂橘子在最角落新鲜橘子在最远的对角那么至少需要n m分钟才能全部感染完。每分钟扫描n × m个格子总复杂度是O((n m) × n × m)。这样的复杂度在数据范围较大时会接近甚至超过一亿次操作在力扣上基本会超时。所以这个思路只能作为理解题意的辅助不适合作为正式提交的解法。2.3 从暴力模拟到BFS的思维转变既然逐分钟模拟的问题在于反复扫描全表那有没有办法只处理“边界”上的格子呢这里就是BFS的切入点。BFS之所以高效是因为每个格子最多入队一次、出队一次访问的总次数是O(n × m)而不是“分钟数 × 格子数”。处理一分钟的传播等价于BFS中处理队列的当前一层处理完这一层再进入下一层。整个搜索一遍完成所有橘子被感染的时间顺序就天然排好了。我个人的体会是从暴力扫描到BFS的转变核心是把思维模式从“全局扫描”切换成“事件驱动”。每一分钟真正需要处理的只是上一轮刚被感染的那些橘子而不是全网格所有格子。队列天然支撑了这个需求新感染的橘子入队下一轮从队列中取出它们再扩散。有了这个认知后面的实现就顺理成章了。3. 多源BFS的完整实现Python和Java双版本逐行解读3.1 整体算法流程实现多源BFS之前先把整体流程写清楚。我分成四步遍历整个网格把所有值为2的格子加入队列同时统计新鲜橘子的数量。用变量记录当前BFS的层数或者说分钟数。进入BFS循环每次处理完当前队列中的所有节点才算过了一分钟。BFS结束后扫描一遍网格如果还有值为1的格子说明有新鲜橘子无法被感染返回-1否则返回分钟数。步骤1里的存在性判断可以提前做如果最初就没有新鲜橘子直接返回0。如果没有腐烂橘子但有新鲜橘子直接返回-1。3.2 Python版本的代码与注释from collections import deque class Solution: def orangesRotting(self, grid: List[List[int]]) - int: rows, cols len(grid), len(grid[0]) queue deque() fresh 0 # 初始化把所有腐烂橘子入队统计新鲜橘子数 for i in range(rows): for j in range(cols): if grid[i][j] 2: queue.append((i, j)) elif grid[i][j] 1: fresh 1 # 如果没有新鲜橘子直接返回0 if fresh 0: return 0 minutes 0 directions [(-1, 0), (1, 0), (0, -1), (0, 1)] while queue and fresh 0: minutes 1 size len(queue) for _ in range(size): x, y queue.popleft() for dx, dy in directions: nx, ny x dx, y dy if 0 nx rows and 0 ny cols and grid[nx][ny] 1: grid[nx][ny] 2 queue.append((nx, ny)) fresh - 1 return minutes if fresh 0 else -1这段代码里最关键的地方有两个。第一个是用 size 记录当前层的节点数因为只有处理完当前层的所有节点才代表这一分钟结束。第二个是循环条件中加了 fresh 0一旦新鲜橘子数量归零就可以提前退出不必再继续处理队列里剩余的节点。提示在 while 循环开头执行 minutes 1而不是在处理完一层之后再加这样可以避免“最后几分钟的额外1”问题。我一开始写成处理完一层再加结果答案总是比预期大1。3.3 Java版本与Python版本的关键差异Java版本的核心逻辑完全一致但因为Java没有Python那么方便的元组和解构代码里的样板代码会更长一些。这里我给出一个干净、可读性优先的版本。class Solution { public int orangesRotting(int[][] grid) { int rows grid.length, cols grid[0].length; Queueint[] queue new LinkedList(); int fresh 0; for (int i 0; i rows; i) { for (int j 0; j cols; j) { if (grid[i][j] 2) { queue.offer(new int[]{i, j}); } else if (grid[i][j] 1) { fresh; } } } if (fresh 0) return 0; int minutes 0; int[][] dirs {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; while (!queue.isEmpty() fresh 0) { minutes; int size queue.size(); for (int i 0; i size; i) { int[] cell queue.poll(); for (int[] d : dirs) { int nx cell[0] d[0], ny cell[1] d[1]; if (nx 0 nx rows ny 0 ny cols grid[nx][ny] 1) { grid[nx][ny] 2; queue.offer(new int[]{nx, ny}); fresh--; } } } } return fresh 0 ? minutes : -1; } }Java版需要注意的一点是Queueint[] 里的数组元素是引用类型poll出来之后可以直接修改不会影响队列里的其他元素因为数组只被当前变量引用一次没有共用风险。这一点在刷题时不会出问题但如果把同一个数组引用加入多个结果集就要小心了。3.4 另一种实现思路直接在格子上记录感染时间除了用队列分层计数还有一种常见的实现方式不用 minutes 变量而是把每个格子被感染的时间直接写到 grid 数组里。初始腐烂橘子对应时间0每次感染新橘子时把 grid[nx][ny] 设为 grid[x][y] 1。BFS结束后扫描整个网格找到最大的时间值就是答案如果还有新鲜橘子则返回-1。这种方式的好处是直观调试时能直接看到每个格子上的“腐烂时间”。我在本地测试时用过这个版本打印网格状态非常方便。缺点是会修改原始数组的语义把1、2、0这些状态位覆盖成时间值所以如果想在函数结束后继续用原数组需要先复制一份。以 Python 为例这个版本可以写成def orangesRotting_timeVersion(self, grid): rows, cols len(grid), len(grid[0]) queue deque() fresh 0 for i in range(rows): for j in range(cols): if grid[i][j] 2: queue.append((i, j)) elif grid[i][j] 1: fresh 1 if fresh 0: return 0 dirs [(-1, 0), (1, 0), (0, -1), (0, 1)] max_time 0 while queue: x, y queue.popleft() for dx, dy in dirs: nx, ny x dx, y dy if 0 nx rows and 0 ny cols and grid[nx][ny] 1: grid[nx][ny] grid[x][y] 1 fresh - 1 queue.append((nx, ny)) max_time max(max_time, grid[nx][ny]) return max_time if fresh 0 else -1这个版本不需要 size 变量因为时间信息直接存在坐标里。它的缺点是在初始化时没有把 max_time 设为0的特殊情况处理所以需要在一开始就排除掉 fresh 0 的情况。整体来说两个版本的时间复杂度相同选择哪个取决于个人习惯。4. 我实际踩过的坑分钟计数、边界检查与DFS的误区4.1 分钟数比预期大1的问题我第一次提交时用了一个“处理完一层再加分钟数”的逻辑结果在测试样例上总是比预期答案大1。为什么因为BFS的层数和传播分钟数之间有一层微妙的偏移关系。假设初始腐烂橘子在第0分钟就已经存在。队列初始包含这些腐烂橘子它们对应的时间是0。如果我在处理完这一层也就是没有任何新感染发生之后才 minutes 1那么最后一次传播结束后的额外加1就是多余的。以只有一个烂橘子、周围有1个新鲜橘子的最简单情况为例第1分钟腐烂橘子感染新鲜橘子。如果我的循环是“先取出一层处理完感染后 minutes 1”那第1分钟的处理会先让新鲜橘子变腐烂然后此刻 minutes 才变成1。看上去好像没问题但如果队列里还有后续节点或者处理过程中 new_fresh 被减到0但循环没有立刻退出就会多算一个分钟。解决方式有几个我选择的是在 while 循环开头直接 minutes 1这样每处理一层就对应一分钟不会多算。如果新感染数在某一轮为0说明这分钟没有任何传播发生循环条件 fresh 0 也会提前退出不会有多余计数。4.2 边界检查少写一个方向方向数组四个方向的写法非常固定上下左右是 (dx, dy) 分别为 (-1,0), (1,0), (0,-1), (0,1)。我一开始写的是三个方向漏掉了向左这一项导致部分区域永远不会被感染测试用例里有一个 [[2,1,1],[1,1,0],[0,1,1]] 的样例答案本应是4我输出的是5甚至更大的数因为左边的橘子一直烂不过来。这类错误写代码时很容易犯因为它不会直接报错只是结果不对。我总结的检查方法是在本地用一组自己手算过的数据去验证比如一个4x4网格手动列一分钟一分钟的传播表然后用代码跑一遍对比输出。如果答案不一致先print队列状态和每个格子的感染时间定位是哪一步的扩散路径出了问题。4.3 用DFS解这道题为什么容易出问题有一个很常见的误区是看到网格上的传播问题就想用DFS。DFS天然适合“是否存在路径”或“连通块大小”这类问题但腐烂橘子要求的是“最早全部感染的时间”也就是最短传播距离。用DFS做最短路径时虽然可以通过记录每个节点的时间值来实现但存在两个问题。第一个问题是DFS会深度优先走一条路走到黑可能先给某个格子赋了一个较大的时间值但后续另一条路径可以更早到达这个格子就需要回溯更新。这就退化成带备忘录的DFS复杂度很难保证。第二个问题是传染是同步发生的。DFS隐含的顺序性会导致“时间”的语义不准确。我在力扣讨论区看到过有人用DFS提交后得到超时或错误结果原因都是这两个。所以这道题的正确姿势就是BFS不要去和DFS较劲。4.4 初始状态为空的边界条件还有一个容易忽略的点是如果网格里根本没有新鲜橘子答案应该是0而不是某个负数或正值。我第一次写的时候没有处理 fresh 0 的情况导致结果是0的测试用例直接报错。同样如果网格里只有新鲜橘子而没有腐烂橘子答案应该是-1因为没有任何源点。这时候如果直接启动 BFS队列为空循环直接退出然后检查 fresh ! 0 就会返回-1逻辑上是自洽的。但为了可读性我建议在一开始就显式处理这两个边界而不是依赖后面的判断。注意力扣的测试用例里包含了很多极端情况比如1x1的网格只有 [[0]]或者只有 [[2]]。这类用例看起来简单但最容易暴露边界条件处理不到位的问题。5. 一题吃透一类题腐烂橘子的题型扩展与同类问题对比5.1 同一道题在面试中的变形腐烂橘子这道题在面试里很少被原封不动地提问更常见的是在它的基础上变换条件。我遇到过或听说过几种变形把“腐烂橘子”换成“病毒传播”本质不变只是把网格状态机换成新的语义。把“上下左右”四个方向换成“八连通”加上对角线改动只有方向数组。把“每分钟传播一次”改成“每轮随机若干次”那就不是BFS能解决的需要模拟。把问题改成“求最快全部感染的源点的个数”之类的优化问题那就升级成了更复杂的数学问题。面试时如果遇到这些变形先稳住核心还是多源BFS。方向数组改了初始源点变了但队列分层遍历的骨架完全一致。5.2 同类网格BFS题目我按照刷题经验整理了几道与腐烂橘子高度同源、可以一起刷的题目方便横向对比。题目难度与腐烂橘子的关系力扣200 岛屿数量中等网格连通块问题但用DFS更直观力扣542 01矩阵中等同样是多源BFS求每个0/1到最近目标的最短距离力扣1162 地图分析中等多源BFS求离陆地的最大海上距离力扣286 墙与门中等会员题多源BFS从门出发求房间距离力扣417 太平洋大西洋水流中等反向BFS从边缘出发向内搜索这些题的共同点是网格是图目标是距离搜索方式是BFS。差别主要在源点是单数还是复数、距离是曼哈顿距离还是自定义距离、搜索方向是从中心向外还是从外向内。5.3 刷了防腐橘子之后我对BFS有了什么新理解做这道题之前我对BFS的理解停留在“从单个源点出发求最短路径”的教科书层面。做完这道题我才真正理解了“多源”“层序”这两个概念在实际问题里是如何协同工作的。层序的意义在于它能精确地刻画“时间步”这一概念。在腐烂橘子问题里层与层之间恰恰对应一个分钟间隔。这种对应关系在很多现实问题里都存在比如社交网络的信息传播、城市交通的拥堵扩散、以及游戏里的感染机制。多源的意义在于多个起点可以同时出发而不需要分成多次搜索来模拟并行扩散。这让我在后面的刷题中养成了一个习惯拿到一道搜索题先问两个问题一是有几个起点二是搜索的目标是距离还是可达性。根据这两个问题的答案基本就能确定是用BFS还是DFS以及是否需要多源。5.4 一道好题的刷法建议最后说说我个人的刷题建议。像腐烂橘子这种一道题承载多个考点的题目我建议不要只追求提交通过就结束而是分三轮来刷。第一轮先按自己思路写一版哪怕超时也要写出来目的是理解题意。第二轮直接写正式版BFS要点是能解释清楚为什么多源、为什么分层、如何避免分钟1的坑。第三轮试着不看书本实现用不同的方式来写比如用记录时间值的版本或Java版本然后比较它们在边界条件处理上的差异。三轮下来这道题背后的思想就内化了。之后遇到 01矩阵、地图分析这类同类题基本可以十分钟内写出正确代码。这也是我推荐把这题纳入热题100的原因——它值得。我在实际刷题中的一个小习惯是每次做完一道题都会在本地建一个最小测试集手动标出每一个预期输出。然后再把代码跑一遍建立一个“先本地验证、再提交力扣”的固定流程。对于腐烂橘子这道题我已经积累了近十个边界样例包括空网格、全腐烂网格、有橘子但在另一块隔离区域的情况。这些样例不只是为了这一题后面刷同类题时也在反复复用。一步一个脚印地积累自己的调试数据库比反复看题解有用得多。