腐烂的橘子

问题

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

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

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

答案

var orangesRotting = function(grid){
    const m=grid.length;
    const n=grid[0].length;
    let ans=0;
    let q=[];
    let fresh=0;
    for(let i=0;i<m;i++){
        for(let j=0;j<n;j++){
            if(grid[i][j]==1){
                fresh++;
            }
            else if(grid[i][j]==2){
                q.push([i,j]);
            }
        }
    }
    while(fresh&&q.length){
        let tmp=q;
        q=[];
        ans++;
        for(const [x,y] of tmp){
            for(const [i,j] of [[x-1,y],[x+1,y],[x,y-1],[x,y+1]]){
                if(i>=0&&i<m&&j>=0&&j<n&&grid[i][j]===1){
                    grid[i][j]=2;
                    q.push([i,j]);
                    fresh--;
                }
            }
        }
    }
    return fresh?-1:ans;
}

扩展

bfs

【BFS 广度优先搜索算法 图的应用 Breadth First Search 数据结构与算法】 https://www.bilibili.com/video/BV1uCH1eoEYP/?share_source=copy_web&vd_source=c7a8c2728d5ed02cdd74fed0dbaa1168