[LeetCode] 994. Rotting Oranges

You are given an m x n grid where each cell can have one of three values:
0 representing an empty cell,
1 representing a fresh orange, or
2 representing a rotten orange.
Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Example 1:

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Example 2:
Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:
Input: grid = [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 10
grid[i][j] is 0, 1, or 2.

腐烂的橘子。

在给定的网格中，每个单元格可以有以下三个值之一：
值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。
返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotting-oranges
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

题目说了是求每个烂橘子四周围的情况，所以思路也是 flood fill 类型的 BFS。这个题跟一般的 BFS 的题目不太一样的地方在于，需要考虑会不会有一直有好橘子不腐烂的情况，所以需要算一下一共有多少个好橘子 count，每次腐烂了需要减去；和需要记录遍历次数 round，因为这是需要返回的参数。

先遍历一遍 input，得到好橘子的个数 count，也将所有的坏橘子的坐标加入 queue。从 queue 中弹出的时候，判断每个坐标的上下左右是否有好橘子，若有，则把他标记为坏橘子，再放回 queue。while 循环跳出的条件是 count == 0 或者 queue 为空。最后判断如果 count 不为 0 则返回 -1，说明一直有好橘子存在；否则则返回轮数 round。

复杂度

时间O(mn)
空间O(mn)

代码

Java BFS实现一

class Solution {
    public int orangesRotting(int[][] grid) {
        int M = grid.length;
        int N = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        int count = 0;
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (grid[i][j] == 1) {
                    count++;
                } else if (grid[i][j] == 2) {
                    queue.offer(new int[] { i, j });
                }
            }
        }

        int round = 0;
        while (count > 0 && !queue.isEmpty()) {
            round++;
            int n = queue.size();
            for (int i = 0; i < n; i++) {
                int[] orange = queue.poll();
                int r = orange[0];
                int c = orange[1];
                if (r - 1 >= 0 && grid[r - 1][c] == 1) {
                    grid[r - 1][c] = 2;
                    count--;
                    queue.offer(new int[] { r - 1, c });
                }
                if (r + 1 < M && grid[r + 1][c] == 1) {
                    grid[r + 1][c] = 2;
                    count--;
                    queue.offer(new int[] { r + 1, c });
                }
                if (c - 1 >= 0 && grid[r][c - 1] == 1) {
                    grid[r][c - 1] = 2;
                    count--;
                    queue.offer(new int[] { r, c - 1 });
                }
                if (c + 1 < N && grid[r][c + 1] == 1) {
                    grid[r][c + 1] = 2;
                    count--;
                    queue.offer(new int[] { r, c + 1 });
                }
            }
        }
        if (count > 0) {
            return -1;
        } else {
            return round;
        }
    }
}

Java BFS实现二，个人觉得这种实现对坐标的管理更容易记住

class Solution {
    public int orangesRotting(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    count++;
                } else if (grid[i][j] == 2) {
                    queue.offer(new int[] { i, j });
                }
            }
        }

        int[][] DIRS = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
        int round = 0;
        while (count > 0 && !queue.isEmpty()) {
            round++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] orange = queue.poll();
                int x = orange[0];
                int y = orange[1];
                for (int[] dir : DIRS) {
                    int newX = x + dir[0];
                    int newY = y + dir[1];
                    // 邻居节点在矩阵内 + 是个好橘子
                    if (newX >= 0 && newX < m && newY >= 0 && newY < n && grid[newX][newY] == 1) {
                        count--;
                        grid[newX][newY] = 2;
                        queue.offer(new int[] { newX, newY });
                    }
                }
            }
        }
        if (count > 0) {
            return -1;
        }
        return round;
    }
}

JavaScript实现

/**
 * @param {number[][]} grid
 * @return {number}
 */
var orangesRotting = function (grid) {
    let q = [];
    let newFresh = 0;
    let minutes = 0;
    // push rotten oranges to the stack and count fresh oranges
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[i].length; j++) {
            if (grid[i][j] === 2) q.push([i, j]);
            if (grid[i][j] === 1) newFresh++;
        }
    }

    while (q.length && newFresh) {
        let newQ = []; // queue for next minute
        while (q.length) {
            let badOrange = q.shift();
            let newRottens = infectOthers(grid, badOrange[0], badOrange[1], newQ);
            newFresh -= newRottens;
        }
        minutes++;
        q = newQ;
    }
    if (newFresh !== 0) return -1;
    return minutes;
};

// Infect surrounding oranges
// Return the number of newly infected oranges
var infectOthers = function (grid, i, j, q) {
    let infected = 0;
    if (i > 0 && grid[i - 1][j] === 1) {
        grid[i - 1][j]++;
        infected++;
        q.push([i - 1, j]);
    }
    if (j > 0 && grid[i][j - 1] === 1) {
        grid[i][j - 1]++;
        infected++;
        q.push([i, j - 1]);
    }
    if (i < grid.length - 1 && grid[i + 1][j] === 1) {
        grid[i + 1][j]++;
        infected++;
        q.push([i + 1, j]);
    }
    if (j < grid[0].length - 1 && grid[i][j + 1] === 1) {
        grid[i][j + 1]++;
        infected++;
        q.push([i, j + 1]);
    }
    return infected;
}