994. Rotting Oranges

Leetcode link

题目简介

/**
 * @param {number[][]} grid
 * @return {number}
 */

题目给我们一个二维数字数组 grid，其中元素有三种可能：

• 0:表示当前格子是空的
• 1:表示当前格子有一个新鲜橘子
• 2:表示当前格子有一个腐烂的橘子

每一分钟过去，腐烂的橘子都会让其上下左右的新鲜橘子腐烂

题目要求我们计算需要用多少时间才能把所有橘子腐烂

如果没办法把所有橘子腐烂则需要返回 -1

解题思路

我们可以遍历整个 grid，对每个腐烂的橘子使用 dfs 遍历起上下左右的新鲜橘子，同时记录时间

不过我们还需要考虑到这种可能性：

211
111
012

所以我们需要加入一个判断：如果有橘子被其他橘子腐烂了，且用时更短，我们需要记录较短的用时

最后，我们需要再次遍历所有的 grid，如果有发现还有新鲜橘子则返回 -1，否则返回用时

Javascript

/**
 * @param {number[][]} grid
 * @return {number}
 */
var orangesRotting = function (grid) {
    const height = grid.length
    const width = grid[0].length
    const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]

    const dfs = (row, col, minute) => {
        // grid[row][col] > 1 && grid[row][col] < minute is the key point
        // it means another rotten orange has rotten this orange in a shorter time, so the current orange should not rot again
        if (row < 0 || row >= height || col < 0 || col >= width || grid[row][col] === 0 ||  (grid[row][col] > 1 && grid[row][col] < minute)) {
            return
        }

        grid[row][col] = minute
        for (const dir of dirs) {
            dfs(row + dir[0], col + dir[1], minute + 1)
        }
    }

    for (let i = 0; i < height; i++) {
        for (let j = 0; j < width; j++) {
            if (grid[i][j] === 2) {
                // we use 2 as base minute and adjust later
                dfs(i, j, 2)
            }
        }
    }

    let res = 2
    for (let i = 0; i < height; i++) {
        for (let j = 0; j < width; j++) {
            if (grid[i][j] === 1) {
                return -1
            }
            res = Math.max(res, grid[i][j])
        }
    }

    return res - 2
};