994. 腐烂的橘子

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

• 值 0 代表空单元格；
• 值 1 代表新鲜橘子；
• 值 2 代表腐烂的橘子。

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

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

示例 1：

输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4

示例 2：

输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。

示例 3：

输入：grid = [[0,2]]
输出：0
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。

链接：https://leetcode.cn/problems/rotting-oranges

解答

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

[
    [2,1,1],
    [1,1,0],
    [0,1,1]
]


[
    [2,1,1],
    [0,1,1],
    [1,0,1]
]

 */
var orangesRotting = function(grid) {
    if (grid.length === 0) {
        return 0;
    }
    
    if (!hasFreshOranges(grid)) {
        return 0;
    }

    let minutes = 0;
    const len = grid.length * grid[0].length;

    for (let i = 0; i < len; i++) {
        const badOrganges = getBadOranges(grid);

        spread(grid, badOrganges);

        minutes += 1;

        if (!hasFreshOranges(grid)) {
            return minutes;
        }
    }

    return -1;
};


function hasFreshOranges(grid) {
    let isExistFresh = false;

    traverse(grid, (item) => {
        if (item === 1) {
            isExistFresh = true;
            return false;
        }
    });

    return isExistFresh;
}

function traverse(grid, callback) {
    for (let i = 0, iLen = grid.length; i < iLen; i++) {
        for (let j = 0, jLen = grid[i].length; j < jLen; j++) {
            const result = callback(grid[i][j], i, j);

            if (result === false) {
                return;
            }
        }
    }
}

function getBadOranges(grid) {
    const badOrganges = [];

    traverse(grid, (item, i, j) => {
        if (item === 2) {
            badOrganges.push([i, j]);
        }
    });

    return badOrganges;
}

function spread(grid, badOrganges) {
    // i 行
    const iLen = grid.length;

    // j 列
    const jLen = grid[0].length;

    badOrganges.forEach(([i, j]) => {
        // 上 (i-1, j)
        if (i - 1 >= 0 && grid[i - 1][j] === 1) {
            grid[i - 1][j] = 2;
        }

        // 下 (i+1, j)
        if (i + 1 < iLen && grid[i + 1][j] === 1) {
            grid[i + 1][j] = 2;
        }

        // 左 (i, j-1)
        if (j - 1 >= 0 && grid[i][j - 1] === 1) {
            grid[i][j - 1] = 2;
        }

        // 右 (i, j+1)
        if (j + 1 < jLen && grid[i][j + 1] === 1) {
            grid[i][j + 1] = 2;
        }
    })
}