LeetCode 994腐烂橘子问题：DFS解法超时的优化方案咨询

阿华AIGC实验室

2026-4-14

嗨，我来帮你捋捋这个问题的优化思路哈～

先给你提个小细节：你写的那个dfs函数其实是BFS实现哦（用了队列+popleft()，这是典型的广度优先搜索逻辑），不过这不是核心问题——你的解法超时的根本原因是重复计算量太大。

先分析下超时的根源

你当前的思路是对每个新鲜橘子（值为1的单元格）单独跑一遍BFS，去找最近的烂橘子需要多久能感染它。假设网格里有k个新鲜橘子，每个BFS最坏情况下要遍历O(mn)个单元格，整体时间复杂度直接冲到O(k*mn)。像你给的10x10例子里，大部分都是新鲜橘子，重复计算的次数直接爆炸，超时是必然的。

最优优化方案：多源BFS（从烂橘子出发反向扩散）

咱们换个思路，从所有初始烂橘子同时出发，主动扩散感染新鲜橘子，这就是多源BFS，整个过程只需要遍历网格一次，时间复杂度是O(mn)，完全不会超时。具体逻辑是：

第一步：先遍历整个网格，把所有初始烂橘子（值为2）的位置加入队列，同时记录它们的初始时间为0；另外统计新鲜橘子的总数，方便最后判断是否有无法感染的橘子。
第二步：用BFS逐层扩散，每次从队列里取出一个烂橘子，向上下左右四个方向检查相邻单元格：
- 如果是新鲜橘子（值为1），就把它标记为烂橘子，感染时间设为当前烂橘子的时间+1，然后把这个新烂橘子加入队列，同时新鲜橘子总数减1。
第三步：BFS结束后，如果还有新鲜橘子没被感染（总数>0），返回-1；否则返回记录的最大感染时间。

具体代码实现

给你写个可直接用的示例代码：

import collections

def orangesRotting(grid):
    m, n = len(grid), len(grid[0])
    q = collections.deque()
    fresh_count = 0
    max_time = 0

    # 初始化队列：把所有初始烂橘子的位置和初始时间0加入队列
    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

    directions = [(1,0), (-1,0), (0,1), (0,-1)]
    # 开始BFS扩散
    while q and fresh_count > 0:
        x, y, time = q.popleft()
        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
                current_time = time + 1
                max_time = max(max_time, current_time)
                q.append((nx, ny, current_time))
    
    # 还有新鲜橘子没被感染就返回-1，否则返回最大时间
    return max_time if fresh_count == 0 else -1