BFS广度优先搜索——994.腐烂的橘子
腐烂的橘子问题解析
问题描述
在给定的网格中，每个单元格可能有三种状态：
0表示空单元格；1表示新鲜橘子；2表示腐烂橘子。 每分钟，腐烂橘子会使其相邻（上下左右）的新鲜橘子腐烂。求所有橘子腐烂所需的最少分钟数，若不可能则返回-1。
解决思路
- 广度优先搜索（BFS）：利用BFS模拟腐烂扩散的过程，每层扩散对应一分钟。
- 初始化处理：统计初始腐烂橘子的位置和新鲜橘子数量。
- 逐层处理：每一轮处理当前所有腐烂橘子，将相邻的新鲜橘子腐烂，并加入队列作为下一层。
- 时间统计：每处理完一层，时间增加一分钟。
- 结果判断：最终检查是否所有新鲜橘子都被腐烂。
代码详细解析
1. 初始化阶段
Python复制
from collections import deque
def orangesRotting(grid):
rows, cols = len(grid), len(grid[0]) # 获取矩阵的行数和列数
fresh_count = 0 # 用于统计新鲜橘子的数量
queue = deque() # 用于 BFS 的队列，存储腐烂橘子的位置-
rows和cols：分别表示矩阵的行数和列数。 -
fresh_count：用于统计矩阵中新鲜橘子的数量。 -
queue：使用双端队列（deque）存储所有腐烂橘子的位置。队列是 BFS 的核心数据结构，用于逐层扩散腐烂的橘子。
2. 遍历矩阵，初始化腐烂橘子和新鲜橘子
Python复制
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2:
queue.append((r, c)) # 腐烂的橘子加入队列
elif grid[r][c] == 1:
fresh_count += 1 # 统计新鲜橘子的数量-
grid[r][c] == 2：如果当前单元格是腐烂的橘子，将其位置（行r和列c）加入队列。 -
grid[r][c] == 1：如果当前单元格是新鲜的橘子，将新鲜橘子的数量加 1。
3. 特殊情况处理
Python复制
if fresh_count == 0:
return 0-
如果矩阵中没有新鲜橘子（
fresh_count == 0），直接返回0，因为不需要任何时间就能完成腐烂。
4. BFS 模拟腐烂过程
Python复制
minutes = 0 # 用于记录腐烂的总时间
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)] # 四个方向：上下左右-
minutes：记录腐烂的总时间。 -
directions：定义了四个方向，用于检查当前橘子的上下左右相邻单元格。
5. BFS 主循环
Python复制
while queue and fresh_count > 0:
minutes += 1 # 每轮 BFS 表示一分钟
for _ in range(len(queue)):
r, c = queue.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_count -= 1 # 新鲜橘子数量减 1
queue.append((nr, nc)) # 将新腐烂的橘子加入队列-
while queue and fresh_count > 0：只要队列中还有腐烂的橘子，并且还有新鲜的橘子未腐烂，就继续模拟。 -
minutes += 1：每轮 BFS 表示一分钟，时间加 1。 -
queue.popleft()：从队列中取出一个腐烂的橘子。 -
for dr, dc in directions：检查当前腐烂橘子的上下左右四个方向。 -
if 0 <= nr < rows and 0 <= nc < cols：确保相邻单元格在矩阵范围内。 -
grid[nr][nc] == 1：如果相邻单元格是新鲜的橘子，将其标记为腐烂（grid[nr][nc] = 2）。 -
fresh_count -= 1：新鲜橘子数量减 1。 -
queue.append((nr, nc))：将新腐烂的橘子加入队列，以便在后续轮次中继续传播。
6. 检查结果
Python复制
return minutes if fresh_count == 0 else -1-
如果所有新鲜橘子都腐烂了（
fresh_count == 0），返回总时间minutes。 -
如果仍有新鲜橘子未腐烂（
fresh_count > 0），返回-1。
示例解析
假设输入矩阵为：
Python复制
grid = [
[2, 1, 1],
[1, 1, 0],
[0, 1, 1]
]-
初始化：
-
腐烂橘子位置：
(0, 0)。 -
新鲜橘子数量：5。
-
-
BFS 过程：
-
第 1 分钟：
-
腐烂橘子
(0, 0)使(0, 1)和(1, 0)腐烂。 -
新鲜橘子数量变为 3。
-
-
第 2 分钟：
-
腐烂橘子
(0, 1)使(0, 2)腐烂。 -
腐烂橘子
(1, 0)使(1, 1)腐烂。 -
新鲜橘子数量变为 1。
-
-
第 3 分钟：
-
腐烂橘子
(1, 1)使(2, 1)腐烂。 -
新鲜橘子数量变为 0。
-
-
-
输出：
-
所有橘子腐烂，返回
3。
-
完整代码
from collections import deque
def orangesRotting(grid):
rows, cols = len(grid), len(grid[0])
fresh_count = 0 # 统计新鲜橘子的数量
queue = deque() # 存储腐烂橘子的队列
# 初始化：遍历网格，记录腐烂橘子和新鲜橘子的状态
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2:
queue.append((r, c))
elif grid[r][c] == 1:
fresh_count += 1
# 若初始时无新鲜橘子，直接返回0
if fresh_count == 0:
return 0
directions = [(0,1), (0,-1), (1,0), (-1,0)] # 四个扩散方向
minutes = 0 # 记录分钟数
# BFS处理腐烂过程
while queue and fresh_count > 0:
minutes += 1 # 每处理完一层，时间+1
for _ in range(len(queue)): # 处理当前层的所有腐烂橘子
r, c = queue.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_count -= 1 # 新鲜橘子减少
queue.append((nr, nc)) # 新腐烂的橘子加入队列
# 判断是否所有橘子都已腐烂
return minutes if fresh_count == 0 else -1总结
通过 BFS 逐层处理腐烂橘子，精确模拟感染过程并统计时间。代码通过队列管理腐烂橘子，利用 fresh_count 判断是否全部腐烂，最终返回结果。此方法高效且直观，是处理网格扩散问题的经典方案。