思路:
思维转化:
第一步先找出所有腐烂的橘子,这些橘子会在上下左右进行感染,然后记录被感染的 橘子,之前感染过的句子不再使用,将新的感染的橘子收集,然后遍历让其上下左右依次感染,没做一次批量感染,时间加1。
直到无法在搜集新的感染橘子的时候,判断感染橘子的总和和橘子的数量是否相等,如果相等返回最小分钟数,如果不相等,说明有些橘子无法被感染,返回-1。
代码如下:
class Solution {
public int orangesRotting(int[][] grid) {
// 如果网格为空或者行或列的长度为0,直接返回0,因为没有橘子。
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int num = 0; // 新鲜橘子的数量
Queue<int[]> queue = new LinkedList<>(); // 用于BFS的队列
int N = grid.length; // 网格的行数
int M = grid[0].length; // 网格的列数
// 遍历整个网格
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
// 如果找到一个腐烂的橘子,就将它的位置加入队列
if (grid[i][j] == 2) {
int[] position = {i, j};
queue.add(position);
}
// 如果找到一个新鲜的橘子,新鲜橘子的数量加一
if (grid[i][j] == 1) {
num++;
}
}
}
// 如果没有新鲜橘子,直接返回0,因为没有橘子需要腐烂
if (num == 0) {
return 0;
}
int count = 0; // 记录所需分钟数
int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 四个可能的移动方向(上下左右)
// 当队列不为空,并且还有新鲜的橘子时,进行BFS
while (!queue.isEmpty() && num > 0) {
int size = queue.size(); // 当前队列的大小,代表这一分钟可以腐烂的橘子数量
for (int i = 0; i < size; i++) {
int[] point = queue.poll(); // 取出一个腐烂的橘子
// 遍历四个方向
for (int[] direction : directions) {
int x = point[0] + direction[0];
int y = point[1] + direction[1];
// 如果相邻的橘子是新鲜的,它就会腐烂
if (x >= 0 && y >= 0 && x < N && y < M && grid[x][y] == 1) {
grid[x][y] = 2; // 标记为腐烂
queue.add(new int[]{x, y}); // 将新腐烂的橘子加入队列
num--; // 新鲜橘子的数量减少
}
}
}
count++; // 每完成一轮BFS,时间增加一分钟
}
// 如果没有新鲜橘子剩余,返回所需的时间,否则返回-1表示有橘子永远不会腐烂
return num == 0 ? count : -1;
}
}