大家好！我是曾续缘😜
今天是《LeetCode 热题 100》系列
发车第 52 天
图论第 2 题
❤️点赞 👍 收藏 ⭐再看，养成习惯

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
示例 1：
输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4
示例 2：
输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上。
示例 3：
输入：grid = [[0,2]]
输出：0
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 10
grid[i][j] 仅为 0、1 或 2
难度：💖💖

解题方法

题目要求在给定的网格中找出腐烂所有新鲜橘子需要的最小分钟数，这是一个经典的广度优先搜索（BFS）问题。

基于一个不影响问题结果的前提：我们的腐烂的橘子最多只会影响一次周围的新鲜橘子，腐烂后我们无需再次处理（队列出队后不会再进队），接下来我们通过 BFS 遍历网格，模拟橘子的腐烂过程，直到没有新鲜橘子为止，从而得出所需的最小分钟数：

首先，我们遍历整个网格，将新鲜橘子的数量计数，并将腐烂的橘子加入队列中。然后我们使用一个队列来进行 BFS。每一轮 BFS 都代表着一分钟的过去，我们遍历当前队列中的所有腐烂橘子，并将它们周围的新鲜橘子腐烂，同时更新新鲜橘子的数量和网格状态。接着进入下一分钟的处理。直到队列为空或者没有新鲜橘子为止。

在代码中，我们使用了 Pair 类来表示二维坐标，在每一轮 BFS 中，我们根据当前腐烂橘子的位置，计算它周围四个方向的坐标，判断是否有新鲜橘子并将其腐烂。同时，我们也用 fresh 变量来记录新鲜橘子的数量，minute 变量记录经过的分钟数。最后根据新鲜橘子的数量返回最小分钟数或者 -1。

Code

查看代码

java

class Solution {
    public int orangesRotting(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        Queue<Pair<Integer, Integer>>q = new LinkedList<Pair<Integer, Integer>>();
        int fresh = 0, minute = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == 1){
                    fresh++;
                }else if(grid[i][j] == 2){
                    q.offer(new Pair<>(i, j));
                }
            }
        }
        int[] d = new int[]{-1, 0, 1, 0, -1};
        while(!q.isEmpty() && fresh > 0){
            int rotten = q.size();
            while(rotten-- > 0){
                Pair<Integer, Integer> cur = q.poll();
                for(int k = 0; k < 4; k++){
                    int i = cur.getKey() + d[k], j = cur.getValue() + d[k + 1];
                    if(i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != 1){
                        continue;
                    }
                    fresh--;
                    grid[i][j] = 2;
                    q.offer(new Pair<>(i, j));
                }
            }
            minute++;
        }
        return fresh == 0 ? minute : -1;
    }
}

解题方法 ​

Code ​

解题方法

Code