1. 问题背景与题目解析
今天想和大家分享一道经典的广度优先搜索（BFS）算法题——LeetCode 994题"腐烂的橘子"。这道题看似简单，但蕴含着很多值得深入思考的算法细节，也是面试中的高频题目。
题目描述是这样的：在一个给定的网格中，每个单元格可以有以下三个值之一：
- 0 代表空单元格
- 1 代表新鲜橘子
- 2 代表腐烂的橘子
每分钟，任何与腐烂橘子相邻（上下左右）的新鲜橘子都会腐烂。我们需要计算直到没有新鲜橘子可以被腐烂为止所需的最小分钟数。如果不可能使所有新鲜橘子都腐烂，则返回-1。
2. 解题思路分析
2.1 问题建模
这道题本质上是一个典型的图论中的多源点广度优先搜索问题。我们可以将网格看作一个图：
- 每个橘子（值为1或2的单元格）是图中的一个节点
- 相邻的橘子之间存在边
- 腐烂过程就是从多个源点（初始腐烂的橘子）开始，向外扩散感染的过程
2.2 算法选择
为什么选择BFS而不是DFS？
- BFS天然适合计算最短路径/最小时间的问题
- 多个腐烂橘子同时影响周围橘子，这符合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
- 新鲜橘子无法被全部感染：返回-1
5.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在多源点最短路径问题中的应用，也提醒我们在处理网格类问题时要注意边界条件和状态更新的时机。
