腐烂的橘子

BraumAce2024年8月3日约 956 字大约 3 分钟

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

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

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

思路

从初始的 $0$ 分钟开始，当前分钟的烂橘子都使其相邻位置的橘子也腐烂，从而不断扩散直到没有新鲜橘子或者无法扩散。

这个过程与广度优先搜索的过程一致，常规的广度优先搜索只有一个起点，而这道题有多个起点，因为烂橘子不止一个，每个烂橘子都会去扩散腐烂周边的新鲜橘子。所以每次扩散需要考虑每一层（即最外层）的烂橘子，使用 size 记录每层烂橘子的数量，将每层的扩散情况都加入队列。

重复上述步骤，即可得到最终的花费时间。

另外，为了判断是否有永远不会腐烂的橘子，我们可以统计初始新鲜橘子的个数 fresh。在 BFS 中，每有一个新鲜橘子被腐烂，就把 fresh 减一，这样最后如果发现 fresh > 0，就意味着有橘子永远不会腐烂，返回 −1。

初始化时间 time = -1，在每层遍历的时候 time++，这样初始的烂橘子时间为 $0$ ，因为它们是本来就有的。但要注意，在全为烂橘子的情况下要返回 0，可是在这种情况下 time 仍为其初始值 $−1$ ，所以最后要返回 $max(time, 0)$ 。

代码

使用链表作为队列，提取BFS方法

class Solution {
    int n, m;
    int g[][];
    int dx[] = {1, 0, -1, 0};    // x方向数组
    int dy[] = {0, 1, 0, -1};    // y方向数组
    int fresh = 0;
    int time = -1;    // 初始化时间为-1
    Queue<Pair<Integer, Integer>> q = new LinkedList<>();

    // 将BFS过程提取为单独的一个方法
    void bfs() {
        while (!q.isEmpty()){
            time++;    // 每遍历一层时间+1
            int size = q.size();

            // 取出这一层的烂橘子开始遍历
            while (size-- > 0){
                Pair<Integer, Integer> t = q.poll();
                int x = t.getKey();
                int y = t.getValue();
                for (int k = 0; k < 4; k++){  // 开始扩散
                    int xx = x + dx[k], yy = y + dy[k];
                    if (xx >= 0 && xx < n && yy >= 0 && yy < m && g[xx][yy] == 1){
                        fresh--;
                        q.offer(new Pair<>(xx, yy));
                        g[xx][yy] = 2;    // 标记变成烂橘子
                    }
                }
            }
        }
    }

    public int orangesRotting(int[][] g) {
        n = g.length;
        m = g[0].length;
        this.g = g;

        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                if (g[i][j] == 1){
                    fresh++;  // 统计新鲜橘子数
                } else if (g[i][j] == 2){
                    q.offer(new Pair<>(i, j));  // 将初始的烂橘子入队
                }
            }
        }

        bfs();

        return fresh > 0 ? -1 : Math.max(time, 0);
    }
}

更简洁的写法 - 使用数组列表作为队列（推荐）

class Solution {
    int dd[][] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; // 四个方向

    public int orangesRotting(int[][] g) {
        int n = g.length;
        int m = g[0].length;
        int fresh = 0;

        List<int[]> q = new ArrayList<>();
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                if (g[i][j] == 1) fresh++;  // 统计新鲜橘子个数
                else if (g[i][j] == 2) q.add(new int[]{i, j});  // 初始的烂橘子
            }
        }

        int time = -1;
        while (!q.isEmpty()) {
            time++;  // 经过一分钟
            List<int[]> tmp = q;  // 取出当前最外层的烂橘子
            q = new ArrayList<>();  // 记录下一层被扩散的烂橘子
            for (int[] pos : tmp) {  // 开始扩散
                for (int[] d : dd) {
                    int i = pos[0] + d[0];
                    int j = pos[1] + d[1];
                    if (0 <= i && i < n && 0 <= j && j < m && g[i][j] == 1) {
                        fresh--;
                        g[i][j] = 2;  // 标记变成烂橘子
                        q.add(new int[]{i, j});  // 加入新的一层
                    }
                }
            }
        }

        return fresh > 0 ? -1 : Math.max(time, 0);
    }
}

腐烂的橘子

腐烂的橘子

题意

思路

代码