Leetcode 腐烂的橘子
使用**广度优先搜索（BFS）**来解决问题。以下是其算法思想的详细解释：
1. 初始化
首先，我们遍历整个 grid 网格，找到所有腐烂的橘子（值为2）和新鲜的橘子（值为1）：
- 如果遇到腐烂的橘子，我们将它的位置坐标加入队列
queue中，作为腐烂扩散的起点。 - 如果遇到新鲜的橘子，我们增加一个计数器
freshOranges来记录新鲜橘子的总数。
2. 特殊情况处理
在遍历网格之后，我们判断新鲜橘子的数量：
- 如果
freshOranges为 0，说明没有新鲜橘子，返回 0，因为不需要任何时间来腐烂。
3. 广度优先搜索（BFS）
使用 BFS 来处理腐烂橘子的扩散。每分钟，队列中的所有腐烂橘子会向它们相邻的四个方向（上、下、左、右）尝试腐烂新鲜橘子。代码的主要逻辑如下：
- 初始化一个二维数组
directions，用于表示四个方向。 - 开始 BFS 循环。每次循环表示 1 分钟的时间。
- 在这一分钟内，遍历当前队列中的所有腐烂橘子。
- 对每个腐烂橘子，从
directions中取出四个方向，检查相邻的格子：- 如果相邻格子有新鲜橘子（值为1），将其变成腐烂（值为2），并将该位置加入队列，同时减少新鲜橘子的计数器
freshOranges。
- 如果相邻格子有新鲜橘子（值为1），将其变成腐烂（值为2），并将该位置加入队列，同时减少新鲜橘子的计数器
- 如果在这一分钟内至少有一个新鲜橘子被腐烂，标记
hasRotten为true，并增加时间计数器minutes。
4. 返回结果
BFS 循环结束后，检查是否还有新鲜橘子：
- 如果
freshOranges为 0，说明所有橘子都已腐烂，返回腐烂所需的总时间minutes。 - 如果
freshOranges仍不为 0，说明有无法腐烂的橘子，返回 -1。
代码整体流程图
- 遍历网格初始化
queue和freshOranges。 - 如果没有新鲜橘子，直接返回 0。
- 通过 BFS 模拟腐烂过程，统计腐烂所需的时间。
- 判断是否有无法腐烂的橘子，决定返回时间或 -1。
class Solution {
public int orangesRotting(int[][] grid) {
//首先遍历grid,判断是否有新鲜的橘子,如果没有,则直接返回0
//同时记录腐烂的橘子的位置坐标
int rows = grid.length;
int cols = grid[0].length;
int freshOranges = 0;
Queue<int[]> queue = new LinkedList<>();
for(int r = 0; r < rows; ++r) {
for(int c = 0; c < cols; ++c) {
if(grid[r][c] == 1) {
freshOranges++;
}else if(grid[r][c] == 2) {
//queue的每个元素是包含2个整数的一维数组,分别是每个腐烂橘子的行,列下标
queue.add(new int[]{r, c});
}
}
}
if(freshOranges == 0) return 0;
//然后开始BFS过程, 需要创建一个方向矩阵,在腐蚀过程中使用
//还需要一个记录返回结果的变量
int minutes = 0;
int[][] directions = {{0, 1},{1, 0},{-1, 0},{0, -1}};
while(!queue.isEmpty()) { //while一遍代表一个minutes的处理过程
int size = queue.size();//size是每个minutes时的腐烂橘子数量
boolean hasRotten = false; //hasRotten是一个标志位,来记录当前分钟是否发生了腐蚀过程
for(int i = 0; i < size; ++i) { //处理每个腐烂橘子的腐烂过程
//获取腐烂橘子的坐标
int[] orange = queue.poll();
int row = orange[0];
int col = orange[1];
//获取到腐烂橘子坐标之后, 开始四个方向的扩散腐烂过程
for(int[] dir: directions) {
int newRow = row + dir[0];
int newCol = col + dir[1];
//首先检查边界条件, 四个邻域不越界且是新鲜橘子才进行腐烂
if(newRow >= 0 && newRow < rows && newCol >= 0 &&
newCol < cols && grid[newRow][newCol] == 1) {
grid[newRow][newCol] = 2;//腐蚀为腐烂的橘子
queue.add(new int[]{newRow, newCol});
freshOranges--;//此消彼长,新鲜橘子减1
hasRotten = true;
}
}
}
if(hasRotten) {
minutes++;
}
}
return freshOranges == 0 ? minutes : -1;
}
}