LeetCode 994. 腐烂的橘子 多源BFS题解，又一道多源BFS，熟悉实现多源BFS。

题目

994. 腐烂的橘子

https://leetcode.cn/problems/rotting-oranges/

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

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

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

BFS+四处发散

思路

关于多源BFS，参考 LeetCode 1162. 地图分析 BFS四处发散题解 。

本题思路较 1162，整体一致，细节方面，需多维护一个新鲜橘子数量，用来判定-1的情况。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

/**
    * 思路：
    * 从腐烂的橘子开始，多源BFS扩散，一直扩散到空位或者边界即可
    * 使用一个变量来维护最大距离
    */
public int orangesRotting(int[][] grid) {
    // 666表示已经访问过了
    int m = grid.length;
    int n = grid[0].length;
    Queue<int[]> pointQ = new ArrayDeque<>();
    int freshCnt = 0;
    for (int row = 0; row < m; row++) {
        for (int col = 0; col < n; col++) {
            if (grid[row][col] == 2) {
                pointQ.offer(new int[]{row, col});
                grid[row][col] = 666;
            }

            if (grid[row][col] == 1) {
                freshCnt++;
            }
        }
    }

    int minutes = 0;
    int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    while (!pointQ.isEmpty() && freshCnt > 0) {
        int size = pointQ.size();

        for (int i = 0; i < size; i++) {
            int[] point = pointQ.poll();
            int x = point[0];
            int y = point[1];

            for (int[] direction : directions) {
                int newX = x + direction[0];
                int newY = y + direction[1];
                if (!inArea(newX, m) || !inArea(newY, n) || grid[newX][newY] == 666 || grid[newX][newY] == 0) {
                    continue;
                }
                // 新鲜橘子变腐烂，同时标记访问状态
                grid[newX][newY] = 666;
                pointQ.offer(new int[]{newX, newY});
                // 某一轮过来的时候可能已经没有新鲜橘子了，此时判断下状态再计数
                freshCnt--;
            }
        }
        minutes++;
    }
    return freshCnt > 0 ? -1 : minutes;
}

private boolean inArea(int x, int m) {
    return x >= 0 && x < m;
}

复杂度分析

时间

根据队列的操作，每个节点入队一次，出队一次，整个规模为矩阵数据量。

时间复杂度：O(m*n)。

空间

访问状态没有使用额外空间，而pointQ最多一次可以发散四个节点，不考虑常数阶，空间复杂度O(1)。

Ref