1. 问题背景与题目解析今天想和大家分享一道经典的广度优先搜索BFS算法题——LeetCode 994题腐烂的橘子。这道题看似简单但蕴含着很多值得深入思考的算法细节也是面试中的高频题目。题目描述是这样的在一个给定的网格中每个单元格可以有以下三个值之一0 代表空单元格1 代表新鲜橘子2 代表腐烂的橘子每分钟任何与腐烂橘子相邻上下左右的新鲜橘子都会腐烂。我们需要计算直到没有新鲜橘子可以被腐烂为止所需的最小分钟数。如果不可能使所有新鲜橘子都腐烂则返回-1。2. 解题思路分析2.1 问题建模这道题本质上是一个典型的图论中的多源点广度优先搜索问题。我们可以将网格看作一个图每个橘子值为1或2的单元格是图中的一个节点相邻的橘子之间存在边腐烂过程就是从多个源点初始腐烂的橘子开始向外扩散感染的过程2.2 算法选择为什么选择BFS而不是DFSBFS天然适合计算最短路径/最小时间的问题多个腐烂橘子同时影响周围橘子这符合BFS的层级遍历特性DFS可能会造成重复计算和不必要的时间浪费2.3 关键变量设计我们需要维护几个关键变量新鲜橘子的计数用于判断最终是否全部腐烂当前腐烂橘子的队列用于BFS遍历时间计数器记录传播的分钟数3. 详细实现步骤3.1 初始化阶段def orangesRotting(grid): rows len(grid) if rows 0: return -1 cols len(grid[0]) fresh 0 queue [] # 初始化统计新鲜橘子数量记录所有腐烂橘子的位置 for r in range(rows): for c in range(cols): if grid[r][c] 1: fresh 1 elif grid[r][c] 2: queue.append((r, c))3.2 BFS处理阶段minutes 0 directions [(-1,0), (1,0), (0,-1), (0,1)] # 上下左右四个方向 while queue and fresh 0: minutes 1 # 处理当前分钟的所有腐烂橘子 for _ in range(len(queue)): r, c queue.pop(0) for dr, dc in directions: nr, nc r dr, c dc if 0 nr rows and 0 nc cols and grid[nr][nc] 1: grid[nr][nc] 2 fresh - 1 queue.append((nr, nc))3.3 结果判断阶段return minutes if fresh 0 else -14. 复杂度分析与优化4.1 时间复杂度最坏情况下需要遍历整个网格O(m×n)每个橘子最多被处理一次O(m×n)总时间复杂度O(m×n)4.2 空间复杂度队列最多存储所有腐烂橘子O(m×n)实际最坏情况下可能达到网格大小4.3 优化思路可以提前终止的条件初始时没有新鲜橘子直接返回0初始时没有腐烂橘子但有新鲜橘子直接返回-1使用双端队列deque代替list可以提高pop(0)的效率5. 边界条件与测试用例5.1 常见边界情况空网格返回-1没有新鲜橘子返回0没有腐烂橘子但有新鲜橘子返回-1新鲜橘子无法被全部感染返回-15.2 测试用例示例测试用例1 [[2,1,1],[1,1,0],[0,1,1]] 预期输出4 测试用例2 [[2,1,1],[0,1,1],[1,0,1]] 预期输出-1 测试用例3 [[0,2]] 预期输出06. 常见错误与调试技巧6.1 常见错误忘记处理初始没有新鲜橘子的情况分钟数计算错误特别是初始分钟应该是0没有正确处理多个腐烂橘子同时扩散的情况边界检查不完整导致数组越界6.2 调试技巧打印每分钟后的网格状态跟踪新鲜橘子数量的变化检查队列处理是否正确特别是层级处理7. 算法扩展思考7.1 变种问题如果橘子腐烂的速度不同比如有些需要2分钟才能腐烂相邻橘子如果橘子可以斜对角传播如果网格非常大如何优化内存使用7.2 实际应用场景疫情传播模型森林火灾蔓延模拟计算机网络中的病毒传播8. 个人实现心得在实际编码中我发现有几个关键点特别容易出错分钟数的增加时机应该在处理完当前所有腐烂橘子后再增加而不是每次处理一个邻居就增加。新鲜橘子的计数必须在将橘子标记为腐烂时就减少计数而不是在处理队列时才计数。层级处理使用for _ in range(len(queue))的技巧来确保正确处理每分钟的层级关系。这道题很好地展示了BFS在多源点最短路径问题中的应用也提醒我们在处理网格类问题时要注意边界条件和状态更新的时机。