Hot 100 ---腐烂的橘子-平芜编程栈

本文概览：本文以LeetCode题目"腐烂的橘子"为例，讲解多源BFS的思路——所有腐烂橘子同时扩散，每轮加1分钟，最后用新鲜橘子计数判断是否全部腐烂

一、题目

二、题目分析

题目要求：每分钟，腐烂的橘子会腐蚀上下左右相邻的新鲜橘子，求全部橘子腐烂的最小时间。如果有橘子永远无法被腐蚀，返回 -1

核心特征：腐烂橘子每分钟向四周扩散一圈，这和上一篇岛屿数量的 BFS 是同一套框架——从起点向外一层层扩散。但有一个关键区别：岛屿数量用 DFS 或 BFS 都行，因为只要标记掉同一个岛屿的所有陆地即可，不关心顺序；而腐烂的橘子只能用 BFS，因为需要计算时间，只有 BFS 的层序遍历才能保证"同一轮扩散的橘子属于同一分钟"

岛屿数量	腐烂的橘子
可用方法	DFS 或 BFS	只能 BFS
起点	遇到一个 ‘1’ 开始	所有腐烂橘子同时开始
扩散目标	标记同一个岛屿的陆地	腐蚀相邻的新鲜橘子
统计	count（岛屿数量）	minutes（轮数 = 分钟数）
无解情况	无	有新鲜橘子永远无法被腐蚀

关键点：腐烂橘子可能有多个，它们同时扩散，所以一开始就要把所有腐烂橘子全部加入队列

思路概览

classSolution{// 上下左右privatefinalint[][]dirs={{1,0},{-1,0},{0,-1},{0,1}};publicintorangesRotting(int[][]grid){if(grid==null||grid.length==0)return0;// 长宽introws=grid.length;intcols=grid[0].length;// 好橘子数intfresh=0;// 队列Queue<int[]>queue=newLinkedList<>();// 加入所有腐烂的橘子for(inti=0;i<rows;i++){for(intj=0;j<cols;j++){// 如果是腐烂的橘子if(grid[i][j]==2){queue.add(newint[]{i,j});}// 如果是好橘子elseif(grid[i][j]==1){fresh++;}}}// 如果没有好橘子if(fresh==0)return0;// 如果有好橘子,开始腐烂returnbfs(grid,queue,rows,cols,fresh);}privateintbfs(int[][]grid,Queue<int[]>queue,introws,intcols,intfresh){intminutes=-1;while(!queue.isEmpty()){intsize=queue.size();// 遍历当前队列中的所有腐烂橘子for(inti=0;i<size;i++){int[]point=queue.poll();// 遍历四个方向for(int[]dir:dirs){intx=point[0]+dir[0];inty=point[1]+dir[1];// 如果越界或者不是好橘子,跳过if(x<0||x>=rows||y<0||y>=cols||grid[x][y]!=1){continue;}// 腐烂橘子grid[x][y]=2;// 好橘子数减一fresh--;// 加入队列queue.add(newint[]{x,y});}}// 分钟数加一minutes++;}// 如果还有好橘子,返回-1if(fresh>0){return-1;}returnminutes;}}

思路简要说明

多源 BFS：先遍历整个网格，把所有腐烂橘子的位置加入队列，同时记录新鲜橘子的数量。这些腐烂橘子就是 BFS 的初始起点
每轮 = 1 分钟：用size记录当前队列长度，一轮处理完当前所有腐烂橘子，minutes+1。这和层序遍历取每层节点数是一个道理
fresh 计数：每腐蚀一个新鲜橘子，fresh-1。BFS 结束后如果 fresh > 0，说明有橘子永远没被腐蚀到，返回 -1

三、思路详解

第一步：为什么是多源 BFS？

普通 BFS 是从一个起点开始扩散。但这题的腐烂橘子可能有多个，而且它们同时向四周扩散。如果对每个腐烂橘子单独做 BFS，时间会出错——因为多个橘子是并行的，不是串行的

解决办法：把所有腐烂橘子一开始就全部加入队列。这样第一轮处理的就是所有初始腐烂橘子，第二轮处理的是它们腐蚀的新橘子，第三轮处理的是新橘子腐蚀的更新橘子……每一轮就是 1 分钟

初始： 第1分钟： 第2分钟： 2 1 1 2 2 1 2 2 2 1 1 0 2 1 0 2 2 0 0 1 1 0 1 1 0 1 1 两个腐烂橘子 四个腐烂橘子 五个腐烂橘子 同时扩散 （各腐蚀了一圈） （继续扩散）

如果分开做 BFS 再取最大值，逻辑会复杂很多。多源 BFS 让所有腐烂橘子在同一个队列里轮转，天然实现了"同时扩散"

第二步：为什么要记录新鲜橘子数量？

这题有个特殊情况：有些新鲜橘子可能永远不会被腐蚀。比如：

2 1 1 0 0 0 1 1 1

上面两行的橘子可以被腐蚀，但下面那行的橘子和上面的腐烂橘子隔了一层空格（0），永远接触不到，所以永远不会腐烂

如果我们只做 BFS，BFS 结束后就不知道还有没有新鲜橘子剩着。所以一开始就要记录新鲜橘子的总数fresh，每腐蚀一个就fresh--。BFS 结束后检查fresh > 0，如果是，说明有橘子没被腐蚀到，返回 -1

第三步：minutes 为什么初始为 -1？

intminutes=-1;while(!queue.isEmpty()){intsize=queue.size();for(inti=0;i<size;i++){// ...处理当前轮}minutes++;}

关键在于理解每一轮 while 循环代表什么：

初始队列里是所有初始腐烂的橘子，它们还没开始扩散，此时是第 0 分钟
第一轮：初始腐烂橘子向四周扩散，腐蚀了第一批新鲜橘子。这批橘子是在第 1 分钟才腐烂的。minutes++→ 0
第二轮：第一批新腐烂橘子继续扩散。minutes++→ 1
…

那 minutes=0 时明明已经腐蚀了第一批，为什么不是 1？因为最后一轮会有一个"空轮"——最后一批腐烂的橘子入队后，它们周围已经没有新鲜橘子了，但仍然会进入 while 循环处理一遍，minutes++多加了一次

所以 -1 的初始值就是为了抵消这个空轮：实际扩散了 N 轮，while 循环跑了 N+1 次（最后一次是空的），minutes = -1 + (N+1) = N，正好是总分钟数

第四步：完整执行过程图解

以这个网格为例：

2 1 1 1 1 0 0 1 1

初始遍历：

腐烂橘子：(0,0) 新鲜橘子数：fresh = 6 队列：[(0,0)]

第 1 轮（处理队列中的 1 个橘子）：

出队 (0,0)，检查上下左右： 下 (1,0) 是 1 → 腐烂，fresh=5，入队 右 (0,1) 是 1 → 腐烂，fresh=4，入队 网格变化： 2 2 1 2 1 0 0 1 1 队列：[(1,0), (0,1)] minutes = 0

第 2 轮（处理队列中的 2 个橘子）：

出队 (1,0)，检查上下左右： 右 (1,1) 是 1 → 腐烂，fresh=3，入队 上 (0,0) 是 2 → 跳过 下 (0,1) 是 0 → 跳过 出队 (0,1)，检查上下左右： 右 (0,2) 是 1 → 腐烂，fresh=2，入队 下 (1,1) 是 2 → 跳过（刚被腐蚀） 左 (0,0) 是 2 → 跳过 网格变化： 2 2 2 2 2 0 0 1 1 队列：[(1,1), (0,2)] minutes = 1

第 3 轮（处理队列中的 2 个橘子）：

出队 (1,1)，检查上下左右： 下 (2,1) 是 1 → 腐烂，fresh=1，入队 其他方向是 0 或 2 → 跳过 出队 (0,2)，检查上下左右： 下 (1,2) 是 0 → 跳过 其他方向越界或 2 → 跳过 网格变化： 2 2 2 2 2 0 0 2 1 队列：[(2,1)] minutes = 2

第 4 轮（处理队列中的 1 个橘子）：

出队 (2,1)，检查上下左右： 右 (2,2) 是 1 → 腐烂，fresh=0，入队 其他方向是 0 或 2 → 跳过 网格变化： 2 2 2 2 2 0 0 2 2 队列：[(2,2)] minutes = 3

第 5 轮（处理队列中的 1 个橘子）：

出队 (2,2)，检查上下左右： 全部越界或 0 或 2 → 无新增 队列为空 minutes = 4

最终检查：fresh = 0，所有橘子都腐烂了，返回 minutes = 4

第五步：和岛屿数量 BFS 的对比

这两题的 BFS 框架几乎一样，关键区别在初始条件和统计目标：

岛屿数量	腐烂的橘子
初始队列	遍历时遇到一个 ‘1’ 才入队	先遍历一遍，所有腐烂橘子全部入队
BFS 调用次数	每个岛屿调用一次	只调用一次
size 的作用	取每层最后一个节点	控制每轮处理几个橘子
轮数的意义	不关心轮数	每轮 = 1 分钟
标记方式	改成 ‘0’	改成 ‘2’（腐烂）
结束后判断	不需要	检查 fresh > 0