图解LeetCode——994. 腐烂的橘子

爪哇缪斯

发布于 2023-09-06 13:41:03

2410

发布于 2023-09-06 13:41:03

文章被收录于专栏：爪哇缪斯

一、题目

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

值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2代表腐烂的橘子。

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

二、示例

2.1> 示例 1：

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

2.2> 示例 2：

【输入】grid = [[2,1,1],[0,1,1],[1,0,1]] 【输出】-1 【解释】左下角的橘子（第 2 行，第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。

2.3> 示例 3：

【输入】grid = [[0,2]] 【输出】0 【解释】因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 10
grid[i][j] 仅为 0、1 或 2

三、解题思路

根据题目描述，我们要计算出单元格中没有新鲜橘子为止所必须经过的最小分钟数。由于腐烂的橘子可以将好的橘子也变腐烂，所以，我们需要采用某种方式，将这种橘子腐烂的轮次模拟计算出来。

这里，我们首先创建一个队列，即：Deque。然后先将矩阵中腐烂的橘子保存到deque中。然后获取deque中存储的腐烂橘子的个数num，那么当num个橘子从deque中出栈之后，就表示该轮次执行完毕。

那么，当我们从队列deque中弹出腐烂的橘子之后，我们会将该烂橘子的上、下、左、右的新鲜橘子都变为烂橘子，即：grid[x][y] = 2。然后将刚刚变烂的句子放入到deque中，准备作为后续下一轮需要操作的烂橘子。

那么，需要补充一点的就是，当我们计算矩阵中腐烂橘子的同时，也可以同时获得新鲜的橘子的个数fresh，当面当我们发现fresh等于0的时候，则说明所有的好橘子都被腐烂了，返回操作的轮次数；而当我们操作完所有的腐烂橘子，而fresh依然不为0，则说明某些新鲜的橘子是不会被传染腐烂的，则直接返回-1即可。

以上就是本题的解题思路。为了方便大家理解，请参照下图图解即可：

四、代码实现

class Solution {
    int fresh = 0, minute = 0;
    Deque<int[]> deque = new ArrayDeque();
    public int orangesRotting(int[][] grid) {
        int result = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 2) deque.addLast(new int[]{i, j});
                if (grid[i][j] == 1) fresh++;
            }
        }
        while (fresh > 0 && !deque.isEmpty()) {
            minute++;
            int nums = deque.size();
            for (int i = 0; i < nums; i++) {
                int[] cell = deque.removeFirst();
                int x = cell[0], y = cell[1];
                rot(grid, x - 1, y); // 查看上方单元格
                rot(grid, x + 1, y); // 查看下方单元格
                rot(grid, x, y - 1); // 查看左侧单元格
                rot(grid, x, y + 1); // 查看右侧单元格
            }
        }
        return fresh > 0 ? -1 : minute; 
    }
    public void rot(int[][] grid, int x, int y) {
        if (x >= 0 && y >=0 && x < grid.length && y < grid[0].length && grid[x][y] == 1) {
            grid[x][y] = 2;
            deque.addLast(new int[]{x, y});
            fresh--;
        }
    }
}