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(gridnull||grid.length0)return0;// 长宽introwsgrid.length;intcolsgrid[0].length;// 好橘子数intfresh0;// 队列Queueint[]queuenewLinkedList();// 加入所有腐烂的橘子for(inti0;irows;i){for(intj0;jcols;j){// 如果是腐烂的橘子if(grid[i][j]2){queue.add(newint[]{i,j});}// 如果是好橘子elseif(grid[i][j]1){fresh;}}}// 如果没有好橘子if(fresh0)return0;// 如果有好橘子,开始腐烂returnbfs(grid,queue,rows,cols,fresh);}privateintbfs(int[][]grid,Queueint[]queue,introws,intcols,intfresh){intminutes-1;while(!queue.isEmpty()){intsizequeue.size();// 遍历当前队列中的所有腐烂橘子for(inti0;isize;i){int[]pointqueue.poll();// 遍历四个方向for(int[]dir:dirs){intxpoint[0]dir[0];intypoint[1]dir[1];// 如果越界或者不是好橘子,跳过if(x0||xrows||y0||ycols||grid[x][y]!1){continue;}// 腐烂橘子grid[x][y]2;// 好橘子数减一fresh--;// 加入队列queue.add(newint[]{x,y});}}// 分钟数加一minutes;}// 如果还有好橘子,返回-1if(fresh0){return-1;}returnminutes;}}思路简要说明多源 BFS先遍历整个网格把所有腐烂橘子的位置加入队列同时记录新鲜橘子的数量。这些腐烂橘子就是 BFS 的初始起点每轮 1 分钟用size记录当前队列长度一轮处理完当前所有腐烂橘子minutes1。这和层序遍历取每层节点数是一个道理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永远接触不到所以永远不会腐烂如果我们只做 BFSBFS 结束后就不知道还有没有新鲜橘子剩着。所以一开始就要记录新鲜橘子的总数fresh每腐蚀一个就fresh--。BFS 结束后检查fresh 0如果是说明有橘子没被腐蚀到返回 -1第三步minutes 为什么初始为 -1intminutes-1;while(!queue.isEmpty()){intsizequeue.size();for(inti0;isize;i){// ...处理当前轮}minutes;}关键在于理解每一轮 while 循环代表什么初始队列里是所有初始腐烂的橘子它们还没开始扩散此时是第 0 分钟第一轮初始腐烂橘子向四周扩散腐蚀了第一批新鲜橘子。这批橘子是在第 1 分钟才腐烂的。minutes→ 0第二轮第一批新腐烂橘子继续扩散。minutes→ 1…那 minutes0 时明明已经腐蚀了第一批为什么不是 1因为最后一轮会有一个空轮——最后一批腐烂的橘子入队后它们周围已经没有新鲜橘子了但仍然会进入 while 循环处理一遍minutes多加了一次所以 -1 的初始值就是为了抵消这个空轮实际扩散了 N 轮while 循环跑了 N1 次最后一次是空的minutes -1 (N1) N正好是总分钟数第四步完整执行过程图解以这个网格为例2 1 1 1 1 0 0 1 1初始遍历腐烂橘子(0,0) 新鲜橘子数fresh 6 队列[(0,0)]第 1 轮处理队列中的 1 个橘子出队 (0,0)检查上下左右 下 (1,0) 是 1 → 腐烂fresh5入队 右 (0,1) 是 1 → 腐烂fresh4入队 网格变化 2 2 1 2 1 0 0 1 1 队列[(1,0), (0,1)] minutes 0第 2 轮处理队列中的 2 个橘子出队 (1,0)检查上下左右 右 (1,1) 是 1 → 腐烂fresh3入队 上 (0,0) 是 2 → 跳过 下 (0,1) 是 0 → 跳过 出队 (0,1)检查上下左右 右 (0,2) 是 1 → 腐烂fresh2入队 下 (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 → 腐烂fresh1入队 其他方向是 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 → 腐烂fresh0入队 其他方向是 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核心都是 BFS 层序遍历的框架只是源从一个变成多个以及统计目标不同复杂度分析时间复杂度O(rows×cols)每个格子最多入队一次空间复杂度O(rows×cols)队列最坏情况存放所有格子