LeetCode 994 腐烂的橘子

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

值 0 代表空单元格；

值 1 代表新鲜橘子；

值 2 代表腐烂的橘子。

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

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

示例 1：

输入：grid = [[2,1,1],[1,1,0],[0,1,1]]

输出：4

示例 2：

输入：grid = [[2,1,1],[0,1,1],[1,0,1]]

输出：-1

解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上。

示例 3：

输入：grid = [[0,2]]

输出：0

解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。

提示：

m == grid.length

n == grid[i].length

1 <= m, n <= 10

grid[i][j] 仅为 0、1 或 2

Python代码：

from typing import List
from collections import dequeclass Solution:def orangesRotting(self, grid: List[List[int]]) -> int:# 网格的行数和列数row_count = len(grid)col_count = len(grid[0]) if row_count > 0 else 0# 存储腐烂橘子的位置，用于广度优先搜索# BFS队列中的每个元素是坐标 (行, 列)rotten_positions = deque()# 统计新鲜橘子的总数，用于判断是否能全部腐烂fresh_oranges = 0# 第一步：遍历网格，初始化队列和新鲜橘子数量for row in range(row_count):for col in range(col_count):# 发现腐烂橘子，加入队列if grid[row][col] == 2:rotten_positions.append( (row, col) )# 发现新鲜橘子，计数加1elif grid[row][col] == 1:fresh_oranges += 1# 特殊情况：如果一开始就没有新鲜橘子，直接返回0if fresh_oranges == 0:return 0# 定义四个扩散方向：上、下、左、右# 每个方向是(行变化量, 列变化量)directions = [ (-1, 0), (1, 0), (0, -1), (0, 1) ]# 记录经过的分钟数minutes_passed = 0# 第二步：BFS扩散，模拟每分钟的腐烂过程# 循环条件：队列中还有腐烂橘子，且还有新鲜橘子while rotten_positions and fresh_oranges > 0:# 当前分钟需要处理的腐烂橘子数量（当前层级的节点数）current_rotten_count = len(rotten_positions)# 处理当前分钟的所有腐烂橘子（确保同一分钟的腐烂同时发生）for _ in range(current_rotten_count):# 取出一个腐烂橘子的位置current_row, current_col = rotten_positions.popleft()# 检查四个方向的相邻单元格for dr, dc in directions:# 计算相邻单元格的坐标new_row = current_row + drnew_col = current_col + dc# 检查相邻单元格是否在网格范围内is_in_grid = (0 <= new_row < row_count) and (0 <= new_col < col_count)# 如果在网格内，且是新鲜橘子if is_in_grid and grid[new_row][new_col] == 1:# 标记为腐烂橘子grid[new_row][new_col] = 2# 新鲜橘子数量减少fresh_oranges -= 1# 将新腐烂的橘子加入队列，用于下一分钟的扩散rotten_positions.append( (new_row, new_col) )# 处理完当前分钟的所有腐烂橘子，时间加1minutes_passed += 1# 第三步：判断结果# 如果所有新鲜橘子都腐烂了，返回所用时间# 否则，返回-1（存在无法腐烂的橘子）return minutes_passed if fresh_oranges == 0 else -1