LeetCode 994腐烂的橘子代码报错：RuntimeError: deque mutated during iteration

问题背景 #

• 练习LeetCode 994《腐烂的橘子》问题提升编程技能
• 此前看过Neetcode的解法视频，尝试独立实现代码
• 解决若干错误后，遭遇RuntimeError: deque mutated during iteration报错，逻辑自洽但无法运行，附上出错代码求助

出错代码示例 #

from collections import deque

def orangesRotting(grid):
    q = deque()
    fresh = 0
    rows, cols = len(grid), len(grid[0])
    
    # 初始化腐烂橘子队列和新鲜橘子计数
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                q.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1
    
    minutes = 0
    # 错误：遍历队列时直接修改队列
    for (r, c) in q:
        directions = [(-1,0), (1,0), (0,-1), (0,1)]
        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
                q.append((nr, nc))
                minutes += 1
    return minutes if fresh == 0 else -1

问题原因 #

RuntimeError: deque mutated during iteration 是因为在迭代deque的过程中直接修改了队列的长度（比如调用append添加新元素）。Python的deque迭代器依赖队列的稳定状态，迭代时队列结构变化会触发该错误。

修复方案 #

正确的BFS需要分层处理每一分钟的腐烂过程：先处理当前队列中所有已有的腐烂橘子（当前分钟的任务），再将新腐烂的橘子加入队列作为下一分钟的任务，避免迭代时修改队列。

修复后的代码：

from collections import deque

def orangesRotting(grid):
    q = deque()
    fresh = 0
    rows, cols = len(grid), len(grid[0])
    
    # 初始化队列和新鲜橘子数量
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                q.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1
    
    minutes = 0
    directions = [(-1,0), (1,0), (0,-1), (0,1)]
    
    # 分层BFS：每一轮处理当前分钟的所有腐烂橘子
    while q and fresh > 0:
        # 记录当前层的元素数量（当前分钟要处理的腐烂橘子数）
        current_level = len(q)
        # 处理当前层的所有元素
        for _ in range(current_level):
            r, c = q.popleft()
            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
                    q.append((nr, nc))
        # 每处理完一层（一分钟），计时加1
        minutes += 1
    
    # 所有新鲜橘子都腐烂则返回时间，否则返回-1
    return minutes if fresh == 0 else -1

关键改进点 #

1. 使用while循环配合current_level分层处理，确保迭代时不会修改当前正在遍历的队列部分
2. 仅在处理完一整层（一分钟的所有腐烂操作）后才增加分钟数，计时逻辑更准确
3. 循环终止条件加入fresh > 0，避免无意义的循环（新鲜橘子已全部腐烂时直接退出）

内容的提问来源于stack exchange，提问作者Moataz Abdelraouf