【一文搞懂多源 BFS 】 : LeetCode994. 腐烂的橘子

【LeetCode Hot 100】994. 腐烂的橘子一文搞懂多源 BFS大家好欢迎来到算法学习专栏。今天我们要聊的是力扣LeetCodeHot 100 中的一道经典题目——994. 腐烂的橘子。这道题是广度优先搜索BFS的经典应用特别是多源 BFS的典型代表。腐烂的橘子目录【LeetCode Hot 100】994. 腐烂的橘子一文搞懂多源 BFS 题目描述 思路分析什么是多源 BFS核心解题步骤代码实现复杂度分析 总结 题目描述在给定的m x n网格中每个单元格可以有以下三个值之一值0代表空单元格值1代表新鲜橘子值2代表腐烂的橘子。规则每分钟腐烂的橘子周围 4 个方向上相邻的新鲜橘子都会腐烂。要求返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能实现即最终还有新鲜橘子无法被腐烂则返回-1。 思路分析看到“每分钟向四周扩散”我们很容易联想到波的扩散过程。这种一层一层向外扩展的特性正是**广度优先搜索BFS**的拿手好戏。再看看这道题的题目要求返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。翻译一下实际上就是求腐烂橘子到所有新鲜橘子的最短路径。那么这道题使用 BFS应该是毫无疑问的了。什么是多源 BFS通常的 BFS 是从一个起点开始扩散。但在这道题中初始状态下可能有多个腐烂的橘子多个源头。怎么办呢很简单我们只需要在 BFS 开始前把所有初始状态为腐烂的橘子的坐标同时放入队列中。让它们作为第一层一起向外扩散这样就能保证所有新鲜橘子被感染的时间是最短且正确的。核心解题步骤统计与初始化遍历整个网格统计新鲜橘子的数量并将所有腐烂橘子的坐标放入队列。分层扩散按分钟计时只要队列不为空且还有新鲜橘子存在就进行循环。每次循环代表过了 1 分钟。我们需要记录当前队列的长度只处理当前这一层的橘子即这一分钟内会传染别人的橘子。对当前层的每个橘子检查其上、下、左、右四个方向。如果是新鲜橘子将其变成腐烂橘子新鲜橘子数量减一并把这个新腐烂的橘子加入队列等待下一分钟继续传染。当前层处理完后时间 1。判断结果队列为空时如果新鲜橘子数量为 0返回消耗的时间。如果新鲜橘子数量仍大于 0说明有些橘子被隔离了无法被传染返回-1。(注视频讲解中UP主口误说返回1实际力扣原题要求返回 -1大家在写代码时要注意哦)代码实现根据上面的思路我们可以写出如下代码以 Python 为例classSolution{// 上下左右四个方向privatestaticfinalint[][]DIRECTIONS{{-1,0},{1,0},{0,-1},{0,1}};publicintorangesRotting(int[][]grid){inttime0;// 经过的分钟数intfresh0;// 剩余新鲜橘子数量Queueint[]qnewArrayDeque();// 存放腐烂橘子坐标的队列// 1. 初始化统计新鲜橘子数量将所有腐烂橘子入队for(inti0;igrid.length;i){for(intj0;jgrid[0].length;j){inttempgrid[i][j];if(temp1){fresh;}elseif(temp2){q.offer(newint[]{i,j});}}}// 没有新鲜橘子直接返回 0if(fresh0){return0;}// 2. 多源 BFS每轮扩散一层对应一分钟while(!q.isEmpty()fresh0){intsizeq.size();time;// 处理当前层的所有腐烂橘子while(size--0){int[]tempq.poll();introwtemp[0];intcoltemp[1];// 向四个方向感染相邻的新鲜橘子for(intj0;j4;j){intnewRowrowDIRECTIONS[j][0];intnewColcolDIRECTIONS[j][1];// 越界或非新鲜橘子跳过if(newRow0||newRowgrid.length||newCol0||newColgrid[0].length||grid[newRow][newCol]!1){continue;}fresh--;grid[newRow][newCol]2;// 标记为腐烂q.offer(newint[]{newRow,newCol});// 入队下一轮继续扩散}}}// 3. 若新鲜橘子已全部腐烂返回时间否则返回 -1returnfresh0?time:-1;}}复杂度分析时间复杂度O ( m × n ) O(m \times n)O(m×n)。我们需要遍历整个网格一次来寻找初始状态BFS 过程中每个单元格最多被访问一次。空间复杂度O ( m × n ) O(m \times n)O(m×n)。最坏情况下网格中全是腐烂的橘子它们会同时被放入队列中。 总结“腐烂的橘子”是一道非常经典的 BFS 模板题。掌握这道题的关键在于理解多源 BFS的思想将多个起始点同时放入队列并利用分层遍历的特性来记录时间步数。只要遇到“最短时间、最少步数、层层扩散”之类的关键词第一时间想到广度优先搜索准没错