本文详解如何将暴力多起点 dfs 改为高效多源 bfs，解决 leetcode 994 腐烂橙子问题，避免重复遍历，将时间复杂度从 o(f·m·n) 降至 o(m·n)，轻松通过大规模网格测试。
本文详解如何将暴力多起点 dfs 改为高效多源 bfs，解决 leetcode 994 腐烂橙子问题，避免重复遍历，将时间复杂度从 o(f·m·n) 降至 o(m·n)，轻松通过大规模网格测试。
在解决「腐烂橙子」这类多起点扩散类问题时，一个常见误区是：对每个新鲜橙子（值为 1）单独执行一次深度优先搜索（DFS），试图反向计算其到最近 rotten 橙子（值为 2）的最短距离。虽然逻辑直观，但该方法存在严重性能缺陷——它本质上是多次 BFS（你代码中实际使用的是队列 + FIFO，属于广度优先，而非 DFS），且每次搜索相互独立，导致大量重复访问和冗余计算。
例如，在一个含 50 个新鲜橙子的 10×10 网格中，你的算法会启动 50 次独立 BFS；而其中许多路径（如靠近中心区域的单元格）会被反复探索数十次，极大拖慢运行速度。根本症结在于：单个新鲜橙子的最短腐烂时间，等价于它到任意一个初始 rotten 橙子的最短曼哈顿距离——这正是经典的「多源最短路径」问题，最优解法是 一次性、多起点、层序扩展的 BFS（即多源 BFS）。
✅ 正确策略：从所有 rotten 橙子同时出发
我们将所有初始值为 2 的坐标一次性加入队列，并以 step = 0 启动 BFS。每一轮遍历当前队列中所有节点（代表「第 step 分钟刚腐烂的所有橙子」），并向四个方向感染相邻的新鲜橙子（grid[i][j] == 1）。关键优化点如下：
- 感染成功后立即将
grid[i_new][j_new]置为2，防止后续重复入队； - 使用
fresh_count实时跟踪剩余新鲜橙子数量，作为终止条件之一； - 每完成一层扩展（即处理完当前分钟所有新腐烂节点），
step自增 1； - 若 BFS 结束后
fresh_count > 0，说明存在无法到达的孤岛，返回-1。
以下是完整、可直接提交的 Python 实现（已适配 LeetCode 环境）：
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] == 1:
fresh_count += 1
elif grid[i][j] == 2:
q.append((i, j, 0))
# 若初始无新鲜橙子，直接返回 0
if fresh_count == 0:
return 0
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
step = -1 # 初始化为 -1，因第一轮扩展对应 minute = 1
while q and fresh_count > 0:
x, y, step = q.popleft()
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <h3>⚠️ 注意事项与进阶提醒</h3>
-
不要修改原题输入？：本解法就地修改
grid以标记已腐烂（1 → 2），符合题目允许范围；若需保持输入不可变，可额外维护visited集合或布尔矩阵，空间开销略增。 -
step初始值为何是-1？：因为首次popleft()取出的是初始 rotten 点（step=0），但此时尚未发生任何「感染动作」；真正第一次感染发生在step + 1 = 1，故最终答案需+1。 - 为什么不是 DFS？：DFS 天然不适合求「最短时间/最少步数」——它可能沿某条长路径深入，错过更近的 rotten 源。BFS 的层序特性天然保证首次到达即为最短距离。
- 时间复杂度：每个单元格最多入队 1 次，总时间复杂度为 O(M×N)；空间复杂度为 O(M×N)（队列最坏存满所有格子）。
该多源 BFS 思路不仅适用于本题，也是解决「地图中多起点扩散」「病毒传播模拟」「多仓库配送最短响应时间」等问题的通用范式。掌握它，意味着你已跨越暴力枚举，步入高效图搜索的实战门槛。
