994. 腐烂的橘子

题目链接：994. 腐烂的橘子

题目描述

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

• 值 0 代表空单元格；
• 值 1 代表新鲜橘子；
• 值 2 代表腐烂的橘子。

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

核心思考：多源广度优先搜索（BFS）

本题是典型的“最短路径”或“扩散过程”问题，最适合使用广度优先搜索（BFS）。

1. 初始状态化：
   • 首先扫描整个网格，统计新鲜橘子的总数 fresh。
   • 寻找所有初始腐烂的橘子坐标，将其加入队列 q。这就是“多源”BFS 的起点。
2. 扩散逻辑：
   • 只要队列不为空且还有新鲜橘子，每一分钟（每一层 BFS）就进行扩散。
   • 每过一分钟，将当前队列中所有的腐烂橘子取出，尝试腐烂其上下左右四个方向的新鲜橘子。
   • 如果某个方向是新鲜橘子（值为 1）：将其变为腐烂（值为 2），新鲜橘子计数 fresh 减 1，并将其加入下一轮的队列。
3. 判别结果：
   • 扩散结束（队列为空）后，如果 fresh 依然大于 0，说明存在无法被波及到的新鲜橘子，返回 -1。
   • 否则返回累计的时间 ans。

解题思路 (Python)

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        fresh = 0
        q = []
        # 初始化统计
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                if x == 1:
                    fresh += 1  # 统计新鲜橘子个数
                elif x == 2:
                    q.append((i, j))  # 初始腐烂的橘子集合（多源起点）

        ans = 0
        # 开始扩散处理
        while q and fresh:
            ans += 1
            temp = q
            q = []
            for x, y in temp:
                # 检查并腐烂四个相邻方向的新鲜橘子
                for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:
                    i, j = x + dx, y + dy
                    if 0 <= i < m and 0 <= j < n and grid[i][j] == 1:
                        fresh -= 1
                        grid[i][j] = 2 # 状态更新
                        q.append((i, j))
        
        return ans if fresh == 0 else -1

复杂度分析

• 时间复杂度：$O(M \times N)$，其中 $M$ 和 $N$ 为网格的行数和列数。在 BFS 过程中，每个格子最多被访问和修改常数次。
• 空间复杂度：$O(M \times N)$。在最坏情况下，队列 q 可能存储几乎全部的橘子坐标。