文章目录前言一、题目1、原题链接2、题目描述二、个人思路整理1、思路分析2、解题代码三、知识风暴前言本专栏文章为《LeetCode 热题 100》的刷题题解相关内容如有侵权立即删除。一、题目1、原题链接994.腐烂的橘子2、题目描述二、个人思路整理1、思路分析核心方法是多源广度优先搜索。具体步骤多源起点腐烂是同时从所有初始腐烂的橘子开始向四周扩散的。因此不能逐个进行单源搜索而需要一开始就把所有初始为 2 的腐烂橘子坐标全部入队。统计新鲜橘子数量在遍历网格初始化队列的同时统计新鲜橘子值为 1的总数fresh_count。若初始fresh_count 0直接返回0分钟。按层扩散BFS每一轮循环代表过去 1 分钟。记录当前队列的大小size依次弹出这批橘子向上下左右 4 个方向扩散。若相邻位置是新鲜橘子值为 1将其置为腐烂改成 2避免重复入队。fresh_count--。将新腐烂的橘子坐标加入队列。只有当本轮确实腐烂了新的橘子时即fresh_count 0且队列非空经过的分钟数minutes才累加。结果判定BFS 结束后若fresh_count 0说明全部腐烂返回minutes若fresh_count 0说明有新鲜橘子被隔绝无法腐烂返回-1。2、解题代码classSolution{public:intorangesRotting(vectorvectorintgrid){intmgrid.size();intngrid[0].size();intfresh_count0;queuepairint,intq;// 1. 初始化收集所有腐烂橘子入队并统计新鲜橘子个数for(inti0;im;i){for(intj0;jn;j){if(grid[i][j]2){q.push({i,j});}if(grid[i][j]1){fresh_count;}}}// 初始就没有新鲜橘子直接耗时 0if(fresh_count0){return0;}intminutes0;intdx[4]{-1,1,0,0};intdy[4]{0,0,-1,1};// 2. 多源 BFS 按层扩散while(!q.empty()fresh_count0){intsizeq.size();minutes;// 每一层代表1分钟for(intk0;ksize;k){auto[x,y]q.front();q.pop();for(intd0;d4;d){intnxxdx[d];intnyydy[d];// 越界或不是新鲜橘子则跳过if(nx0nxmny0nyngrid[nx][ny]1){grid[nx][ny]2;// 标记为已腐烂防止重复访问fresh_count--;q.push({nx,ny});}}}}// 3. 判断是否还有未被感染的新鲜橘子returnfresh_count0?minutes:-1;}};复杂度分析时间复杂度O ( m × n ) O(m \times n)O(m×n)。每个单元格最多被访问和入队常数次。空间复杂度O ( m × n ) O(m \times n)O(m×n)。队列中最多同时存放O ( m × n ) O(m \times n)O(m×n)个坐标。三、知识风暴多源广度优先搜索Multi-source BFS是本题的核心解法。与单源 BFS 不同本题的腐烂过程是同时从所有初始腐烂的橘子开始的因此需要把所有腐烂橘子作为起点统一入队再按层向外扩散。理解多源 BFS 的分层思想对掌握本题至关重要。算法核心思想多源起点腐烂是同时发生的不能逐个进行单源搜索而应一开始就把所有初始为 2 的腐烂橘子坐标全部入队让它们在同一时刻向四周扩散。按层扩散每一轮循环代表过去 1 分钟。记录当前队列大小size只弹出这一批橘子向上下左右 4 个方向扩散保证“分钟数”与“层数”一一对应。原地标记把新鲜橘子置为 2腐烂既避免重复入队又省去了额外的visited数组空间复杂度更优。常见对比单源 BFS vs 多源 BFS单源 BFS从一个起点出发求到其他点的最短距离队列初始只有一个元素。多源 BFS从多个起点同时出发求“所有起点到目标点的最短距离”队列初始包含所有起点。本题中所有腐烂橘子同时扩散天然契合多源 BFS 模型。共同点两者都借助队列按层遍历区别仅在于初始入队的节点数量。多源 BFS 可看作“虚拟超级源点”连接所有起点后的单源 BFS。“按层扩散”标记思想核心思想每一轮循环只处理当前队列中的节点即同一分钟新腐烂的橘子通过size变量固定本轮范围避免把下一分钟才腐烂的橘子混入本轮计数。与本题的联系每经过一轮循环minutes加 1代表又过去 1 分钟。只有本轮确实腐烂了新的橘子fresh_count 0且队列非空分钟数才累加。注意事项若在 BFS 过程中直接修改grid为 2需确保不会把“本轮新腐烂”的橘子当作“下一轮起点”重复扩散——这正是按层处理先记录size的意义所在。使用要点方向数组用int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1};统一表示上下左右四个方向配合循环遍历可避免重复书写四行扩散逻辑。边界检查扩散前务必判断行列下标是否越界以及当前格子是否为新鲜橘子值为 1这是防止重复访问和越界的关键。计数时机新鲜橘子计数器fresh_count--必须放在“发现新鲜橘子并置为腐烂”的瞬间同时入队保证每个橘子只被感染一次。结果判定BFS 结束后若fresh_count 0说明全部腐烂返回minutes若仍有剩余说明有新鲜橘子被隔绝返回-1。算法变体与扩展岛屿数量LeetCode 200单源 DFS/BFS 遍历连通分量与本题的多源 BFS 形成对比可体会“单源 vs 多源”的差异。被围绕的区域LeetCode 130从边界出发标记不被包围的O再翻转其余O是“从边界反向搜索”的经典应用。太平洋大西洋水流问题LeetCode 417从边界反向 DFS标记能到达两个海洋的格子进一步体会“逆向搜索”思想。地图分析LeetCode 1162多源 BFS 求“离所有陆地最远的海洋”与本题同属多源 BFS 的典型应用可加深对分层遍历的理解。相关 LeetCode 例题200. 岛屿数量单源 DFS/BFS 统计连通块130. 被围绕的区域边界反向搜索417. 太平洋大西洋水流问题多源逆向 DFS1162. 地图分析多源 BFS 分层扩散