994. Rotting Oranges

[Tcdian]

994. Rotting Oranges

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

值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。

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

Example 1

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

Example 2

Input: [[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: [[0,2]]
Output: 0
Explanation:  Since there are already no fresh oranges at minute 0, the answer is just 0.

Note

• 1 <= grid.length <= 10
• 1 <= grid[0].length <= 10
• grid[i][j] is only 0, 1, or 2.

[Tcdian]

Solution

• JavaScript Solution

const OrangeStatus = {
    empty: 0,
    fresh: 1,
    rotten: 2,
}

/**
 * @param {number[][]} grid
 * @return {number}
 */
var orangesRotting = function(grid) {
    let [queue, freshOranges] = calcOranges(grid);
    let minute = 0;
    dfs();
    return freshOranges > 0 ? -1 : minute;

    function calcOranges(grid) {
        const queue = [];
        let freshOranges = 0;
        for (let i = 0; i < grid.length; i++) {
            for (let j = 0; j < grid[0].length; j++) {
                if (grid[i][j] === OrangeStatus.fresh) {
                    freshOranges += 1;
                } else if (grid[i][j] === OrangeStatus.rotten) {
                    queue.push([i, j]);
                }
            }
        }
        return [queue, freshOranges];
    }

    function dfs() {
        const direction = [-1, 0, 1, 0, -1];
        while (queue.length > 0 && freshOranges > 0) {
            const n = queue.length;
            for (let i = 0; i < n; i++) {
                const [x, y] = queue.shift();
                for (let d = 0; d < 4; d++) {
                    const directionX = direction[d] + x;
                    const directionY = direction[d + 1] + y;
                    if (
                        directionX >= 0 && directionX < grid.length
                            && directionY >= 0 && directionY < grid[0].length
                            && grid[directionX][directionY] === OrangeStatus.fresh
                    ) {
                        grid[directionX][directionY] = OrangeStatus.rotten;
                        queue.push([directionX, directionY]);
                        freshOranges -= 1;
                    }
                }
            }
            minute += 1;
        }
    }
};

• TypeScript Solution

enum OrangeStatus {
    empty,
    fresh,
    rotten,
}

function orangesRotting(grid: number[][]): number {
    let [queue, freshOranges] = calcOranges(grid);
    let minute = 0;
    dfs();
    return freshOranges > 0 ? -1 : minute;

    function calcOranges(grid: number[][]): [[number, number][], number] {
        const queue: [number, number][] = [];
        let freshOranges = 0;
        for (let i = 0; i < grid.length; i++) {
            for (let j = 0; j < grid[0].length; j++) {
                if (grid[i][j] === OrangeStatus.fresh) {
                    freshOranges += 1;
                } else if (grid[i][j] === OrangeStatus.rotten) {
                    queue.push([i, j]);
                }
            }
        }
        return [queue, freshOranges];
    }

    function dfs() {
        const direction = [-1, 0, 1, 0, -1];
        while (queue.length > 0 && freshOranges > 0) {
            const n = queue.length;
            for (let i = 0; i < n; i++) {
                const [x, y] = queue.shift() as [number, number];
                for (let d = 0; d < 4; d++) {
                    const directionX = direction[d] + x;
                    const directionY = direction[d + 1] + y;
                    if (
                        directionX >= 0 && directionX < grid.length
                            && directionY >= 0 && directionY < grid[0].length
                            && grid[directionX][directionY] === OrangeStatus.fresh
                    ) {
                        grid[directionX][directionY] = OrangeStatus.rotten;
                        queue.push([directionX, directionY]);
                        freshOranges -= 1;
                    }
                }
            }
            minute += 1;
        }
    }
};