LC994　腐烂的橘子¶

中等通过率 55.7%python3核心代码模式图论样例通过牛客 AC广度优先搜索数组矩阵

一句话

所有烂橘子同时作起点做多源 BFS，扩展的层数就是所需分钟数。

解题思路¶

这题考什么¶

腐烂每分钟向四邻各推进一格，这正是 BFS（广度优先搜索）一层一层向外扩的过程： BFS 第 k 层的格子，恰好是距离最近的某个初始烂橘子 k 步的格子。多个烂橘子同时开始，就把它们全部放进初始队列（多源 BFS）—— 等价于虚构一个超级源点连向每个烂橘子，从它出发的距离就是「被哪个烂橘子最先波及」。

2 1 1          第 0 分钟只有 (0,0) 是烂的
1 1 0     ->   第 1 分钟 (0,1) (1,0) 烂；第 2 分钟 (0,2) (1,1)
0 1 1          第 3 分钟 (2,1)；第 4 分钟 (2,2)  -> 答案 4

答案是最后一层的层号，所以要按层推进：一次性取出当前队列里的全部格子作为一层，处理完再把分钟数加一。逐个出队并给每个点记距离也可以，但按层写更贴合「每分钟同时腐烂」的语义。

判 -1 靠计数而不是再扫一遍：先数出新鲜橘子的总数，每腐烂一个就减一，队列耗尽后还剩下的就是四邻永远够不着的孤立橘子。

网格 BFS 的通用框架见 BFS 广度优先搜索。

数据规模与复杂度¶

1 <= m, n <= 10，最多 100 格。每格最多入队一次、出队一次并查四个方向，时间 O(mn) = 100 级别，空间 O(mn) 存队列。这个规模下怎么写都不会超时，重点全在边界判断上。

坑在哪¶

一开始就没有新鲜橘子（全是空格或全是烂橘子）时必须返回 0，不是 -1。示例 3 的 [[0,2]] 正是这一档。写成「先 BFS 再判还有没有新鲜的」也能过，但 fresh 初值为 0 时循环压根不该执行，直接让分钟数保持 0 最省事。
分钟数的累加位置极易多算一层。本文件把加一放在整层扩展之后，看着像会多加：最后一层若一个新橘子都没点燃，队列扩不出下一层，这一分钟仍被记上。它之所以无害，是因为「点燃不出新橘子」蕴含 fresh 仍大于 0，函数走的是 -1 分支，那个偏大的 minutes 根本用不到；而真正返回 minutes 的那条路径（fresh 被减到 0）恰好是最后一层刚点燃完，加一正确。若把循环条件里的 fresh 去掉，队列空之前会白转一层，返回值就真的多 1 了。
空格 0 不能被腐烂，也不能当作通路。只把值为 1 的邻居入队，把 0 也当成可扩展格会让分钟数偏大，还会把隔着空格的橘子误判成可达。
腐烂标记要在入队时写成 2，不能等出队再写。出队才改的话，同一个新鲜橘子会被多个烂邻居重复入队，fresh 被减到负数，最后判不出 -1。
网格值是整数 0/1/2，与 LC200 的字符网格不同，比较时不要加引号。

样例复核¶

示例 2 的 [[2,1,1],[0,1,1],[1,0,1]]：初始新鲜橘子 6 个，唯一的烂橘子在 (0,0)。第 1 分钟点燃 (0,1)，第 2 分钟 (0,2) 与 (1,1)，第 3 分钟 (1,2)，第 4 分钟 (2,2)，共点燃 5 个。左下角 (2,0) 的两个邻居 (1,0) 与 (2,1) 都是空格 0，腐烂永远传不过去，队列耗尽时 fresh 仍为 1，返回 -1，与样例一致。

参考实现¶

solutions/leetcode/LC994/sol.py
from collections import deque
from typing import List, Optional


class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        # 一趟扫描同时做两件事：把全部烂橘子收进初始队列，数清新鲜橘子还剩几个
        q = deque()
        fresh = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 2:
                    q.append((i, j))
                elif grid[i][j] == 1:
                    fresh += 1

        minutes = 0
        # 循环条件带 fresh：没有新鲜橘子时一分钟都不该走，直接给出 0（示例 3）
        while q and fresh:
            # 一次性把当前整层取空，这一层就是「同一分钟内腐烂的那批橘子」
            for _ in range(len(q)):
                x, y = q.popleft()
                for nx, ny in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
                    # 边界先判；值为 0 的空格不导通，只有新鲜橘子会被点燃
                    if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1:
                        # 入队即标 2 并扣减计数，避免同一格被多个烂邻居重复入队
                        grid[nx][ny] = 2
                        fresh -= 1
                        q.append((nx, ny))
            # 加一放在整层扩展之后。本层若一个都没点燃，fresh 必然仍大于 0，
            # 结果走 -1 分支，这次多记的一分钟不会被读到
            minutes += 1

        # 队列耗尽仍有新鲜橘子，说明它们被空格隔断，四邻永远够不着
        return -1 if fresh else minutes

LC994 腐烂的橘子¶