腐烂的橘子
2026年4月21日大约 2 分钟
腐烂的橘子
使用的方法
BFS（广度优先搜索）
解题思路
- 给定一个二维网格，其中每个单元格可以是以下三种状态之一：
- 0：表示空单元格
- 1：表示新鲜橘子
- 2：表示腐烂的橘子
- 每分钟，任何与腐烂橘子相邻（4 个方向）的新鲜橘子都会变成腐烂的橘子。我们需要计算至少需要多少分钟才能使所有新鲜橘子变成腐烂的橘子。如果不可能使所有新鲜橘子变成腐烂的橘子，则返回 -1。
- 我们可以使用广度优先搜索（BFS）来解决这个问题。首先，我们将所有初始腐烂的橘子加入一个队列中，并统计新鲜橘子的数量。
- 然后，我们进行 BFS，每次从队列中取出当前腐烂的橘子，并将其相邻的新鲜橘子变成腐烂的橘子，并将这些新腐烂的橘子加入队列中。
- 每次处理完一层 BFS，表示过了一分钟。我们继续进行 BFS，直到队列为空或者没有新鲜橘子了。
- 最后，如果还有新鲜橘子，说明无法全部腐烂，返回 -1；否则返回总共经过的分钟数。
代码实现
class Solution {
public int orangesRotting(int[][] grid) {
// 网格的行数和列数
int M = grid.length;
int N = grid[0].length;
// 队列用于 BFS，存放当前已经腐烂的橘子坐标
Queue<int[]> queue = new LinkedList<>();
// count 用来记录新鲜橘子的数量
int count = 0;
// 遍历整个网格：
// 1. 统计新鲜橘子数量
// 2. 把初始腐烂橘子加入队列，作为 BFS 的起点
for (int r = 0; r < M; r++) {
for (int c = 0; c < N; c++) {
if (grid[r][c] == 1) {
count++;
} else if (grid[r][c] == 2) {
queue.add(new int[]{r, c});
}
}
}
// round 表示腐烂传播了多少分钟
int round = 0;
// 只要还有新鲜橘子，并且队列里还有腐烂橘子可继续传播，就继续 BFS
while (count > 0 && !queue.isEmpty()) {
// 每进入一层 BFS，表示过了 1 分钟
round++;
// 当前层的腐烂橘子数量
int n = queue.size();
// 遍历这一分钟内所有会传播腐烂的橘子
for (int i = 0; i < n; i++) {
int[] orange = queue.poll();
int r = orange[0];
int c = orange[1];
// 上
if (r - 1 >= 0 && grid[r - 1][c] == 1) {
grid[r - 1][c] = 2; // 变腐烂
count--; // 新鲜橘子数减 1
queue.add(new int[]{r - 1, c}); // 加入下一层 BFS
}
// 下
if (r + 1 < M && grid[r + 1][c] == 1) {
grid[r + 1][c] = 2;
count--;
queue.add(new int[]{r + 1, c});
}
// 左
if (c - 1 >= 0 && grid[r][c - 1] == 1) {
grid[r][c - 1] = 2;
count--;
queue.add(new int[]{r, c - 1});
}
// 右
if (c + 1 < N && grid[r][c + 1] == 1) {
grid[r][c + 1] = 2;
count--;
queue.add(new int[]{r, c + 1});
}
}
}
// 如果最后还有新鲜橘子，说明无法全部腐烂，返回 -1
if (count > 0) {
return -1;
} else {
// 否则返回总共经过的分钟数
return round;
}
}
}