本文介绍如何将针对腐烂橙子问题（leetcode 994）的低效单点 dfs 改为高效多源 bfs，避免重复计算，将时间复杂度从 o(f·m·n) 降至 o(m·n)，显著提升大规模网格下的运行性能。
本文介绍如何将针对腐烂橙子问题（leetcode 994）的低效单点 dfs 改为高效多源 bfs，避免重复计算，将时间复杂度从 o(f·m·n) 降至 o(m·n)，显著提升大规模网格下的运行性能。
在解决「腐烂的橙子」这类网格中多起点、同步扩散类问题时，一个常见但低效的思路是：对每个新鲜橙子（值为 1）单独执行一次深度优先搜索（DFS），试图回溯找到离它最近的腐烂橙子（值为 2）并计算最短距离。这种做法看似直观，实则存在严重性能瓶颈——当网格中新鲜橙子数量较多（如 10×10 示例中含 70+ 个 1）时，会触发多达数十次独立搜索，而不同搜索路径高度重叠，大量重复访问相同格子，导致时间复杂度退化为 O(F × M × N)（F 为新鲜橙子数），极易超时。
值得注意的是，原实现中虽名为 dfs，实际使用的是队列 + 先进先出逻辑，本质是广度优先搜索（BFS）。但问题不在于遍历方式，而在于搜索方向与起点设计：从新鲜橙子反向找腐烂源，是“分散发起、各自探索”；而最优解应采用多源 BFS（Multi-source BFS）——即一次性将所有腐烂橙子作为初始层入队，让腐烂效果从所有源头同步、逐层向外扩散。
该策略的核心优势在于：
- ✅ 一次遍历覆盖全局：每个格子最多被访问一次（一旦变为腐烂，即标记并跳过后续访问）；
- ✅ 天然保证最短时间：BFS 层序特性确保首次到达某新鲜橙子的步数即为其最早腐烂时刻；
- ✅ 动态剪枝：通过维护
fresh_count实时跟踪剩余新鲜橙子数量，可在腐烂完成时立即终止，无需遍历全部状态。
以下是优化后的完整实现（Python）：
from collections import deque
from typing import List
def orangesRotting(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
fresh_count = 0
q = deque()
# 一次性收集所有腐烂橙子坐标，并统计新鲜橙子总数
for i in range(m):
for j in range(n):
if grid[i][j] == 2:
q.append((i, j, 0))
elif grid[i][j] == 1:
fresh_count += 1
# 若初始无新鲜橙子，直接返回 0
if fresh_count == 0:
return 0
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
max_minutes = 0
while q:
x, y, step = q.popleft()
max_minutes = max(max_minutes, step) # 记录当前已传播的最大分钟数
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1:
grid[nx][ny] = 2 # 标记为腐烂，防止重复访问
fresh_count -= 1
q.append((nx, ny, step + 1))
# 若仍有新鲜橙子未被腐烂，说明无法全部感染
return -1 if fresh_count > 0 else max_minutes⚠️ 关键注意事项：
- 不可复用原网格做多次 DFS：每次 DFS 前需深拷贝或重置状态，否则污染数据；而多源 BFS 天然只需一次修改；
-
避免使用
step作为循环变量名与索引冲突：示例中for i, row in ...内部若再用i易引发 bug，建议统一使用x/y或r/c； -
边界判断需前置：先检查坐标合法性，再读取
grid[nx][ny]，防止越界异常； -
初始化
max_minutes = 0更安全：当仅有一个腐烂橙子且无新鲜橙子时，step可能未更新，直接返回0符合题意。
总结而言，面对网格中“多起点同步扩散”问题（如病毒传播、信号覆盖、水漫金山等），应本能优先考虑多源 BFS而非单点 DFS/BFS。它不仅代码简洁、逻辑清晰，更以线性时间复杂度达成最优解，是算法工程师必须掌握的经典范式。
