【一文搞懂多源 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的思想将多个起始点同时放入队列并利用分层遍历的特性来记录时间步数。只要遇到“最短时间、最少步数、层层扩散”之类的关键词第一时间想到广度优先搜索准没错

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

相关推荐

NSK紧凑型大导程滚珠丝杠技术解析

阿里云微服务引擎 MSE 及 API 网关 2026 年 6 月产品动态

合理用药系统的技术架构解析

更多资讯

RPCS3 自动更新机制深度解析：从版本检测到一键升级的完整指南

CVAT 数据标注：一条命令部署，AI 预标注帮你干完粗活

Grasscutter 动漫游戏私服资源包部署完全指南：从零配置到正常登录

SpringBoot3整合FastJSON2：手动配置MessageConverters指南

【多智能体】基于 o3-mini 和 Gemini 的多模态 AI 编程智能体团队

Data Science For Beginners：数据科学生命周期入门——捕获、处理与维护三大核心阶段

今日更新

CopilotKit Vue Demo 与 React Demo 的 Parity 实现指南：路由、运行时端点与交互语义的全框架对齐

Harbor RBAC 实战：db_auth 模式下非管理员用户管理项目成员的完整验证与权限模型解析

STM32平衡车纯平衡程序从拆包到参数整定的完整调试指南

本周精选

超人会飞不算本事：系统稳定依赖清晰规则与边界设计

超人VS蜘蛛侠：拆解超级IP的影响力与传播方法论

基于CNN的调制信号识别：MATLAB实现时频图分类实战

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？