腐烂的橘子

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

• 值 0 代表空单元格；
• 值 1 代表新鲜橘子；
• 值 2 代表腐烂的橘子。
  每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

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

示例1:

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

解题思路

使用广度优先搜索（BFS）算法来模拟腐烂的橘子的传播过程。
PS: 广度优先搜索（BFS）算法一般使用
Queue queue = new LinkedList<>();
搭配 while(!queue.isEmpty())来实现
因为队列的先进先出（FIFO）特性恰好符合 BFS 的搜索顺序。

• 1、遍历整个网格，将腐烂的橘子的坐标加入队列，并统计新鲜橘子的数量。
• 2、在队列不为空的情况下，从队列中取出腐烂的橘子，将其周围未腐烂的橘子腐烂，并将其坐标加入队列。
• 3、每次从队列中取出橘子时，时间变量加一。
• 4、在每次遍历完整个队列时，检查是否还有新鲜橘子没有被腐烂。
• 如果有，则返回 -1。
• 如果没有，则返回时间变量减一，因为最后一个橘子腐烂不需要再等待一分钟。

Java实现

public class RottingOranges {public int orangesRotting(int[][] grid) {int m = grid.length;int n = grid[0].length;int freshOranges = 0; // 记录新鲜橘子的数量Queue<int[]> queue = new LinkedList<>(); // 用于存储腐烂的橘子的位置// 统计新鲜橘子的数量，并将腐烂的橘子加入队列for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 1) {freshOranges++;} else if (grid[i][j] == 2) {queue.offer(new int[]{i, j});}}}int minutes = 0; // 记录经过的分钟数int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上下左右四个方向// 开始进行 BFS，直到队列为空或者没有新鲜橘子为止while (!queue.isEmpty() && freshOranges > 0) {int size = queue.size();//当前腐烂的桔子for (int i = 0; i < size; i++) {int[] curr = queue.poll();//计算上下左右腐烂的桔子for (int[] dir : directions) {int newX = curr[0] + dir[0];int newY = curr[1] + dir[1];if (newX >= 0 && newX < m && newY >= 0 && newY < n && grid[newX][newY] == 1) {grid[newX][newY] = 2; // 标记为腐烂的橘子queue.offer(new int[]{newX, newY});freshOranges--; // 每腐烂一个橘子，新鲜橘子数量减一}}}minutes++; // 经过一分钟}return freshOranges == 0 ? minutes : -1;}public static void main(String[] args) {RottingOranges oranges = new RottingOranges();int[][] grid = {{2, 1, 1},{1, 1, 0},{0, 1, 2}};System.out.println("Minimum minutes required: " + oranges.orangesRotting(grid));}
}

时间空间复杂度

• 时间复杂度：O(m * n)，其中 m 和 n 分别是网格的行数和列数，因为需要遍历整个网格。

• 空间复杂度：O(m * n)，在最坏的情况下，队列的大小可能会达到网格中所有新鲜橘子的数量，因此空间复杂度是 O(m * n)。