乐趣区

关于javascript:Leetcode542矩阵广度遍历解法

给定一个由 0 和 1 组成的矩阵 mat,请输入一个大小雷同的矩阵,其中每一个格子是 mat 中对应地位元素到最近的 0 的间隔。

两个相邻元素间的间隔为 1。

答题

/**

 * @param {number[][]} mat

 * @return {number[][]}
   */
   var updateMatrix = function(mat) {let map = new Array(mat.length);    // 用于输入的数组
   let quque = [];                     // 队列
    /* 给 map 赋初值 */
   for(let i = 0; i < mat.length; i++){map[i] = new Array(mat[0].length).fill(Infinity);
       for(let j = 0; j < mat[0].length; j++){if(mat[i][j] == 0){quque.push([i,j]);
               map[i][j] = 0;
           }
       }
   }
   /* 遍历 0 周边的数,如果大于 0 +1,则赋值,将此推动队列,持续遍历 */
    while(quque.length > 0){
        let size = quque.length;
        for(let k = 0; k < size; k++){let [i,j] = quque.shift();
           

            if(i - 1 >= 0 && map[i - 1][j] > map[i][j] + 1){map[i - 1][j] = map[i][j] + 1;
                quque.push([i - 1,j])
            }
            if(i + 1 < map.length && map[i + 1][j] > map[i][j] + 1){map[i + 1][j] = map[i][j] + 1;
                quque.push([i + 1,j])
            }
            if(j - 1 >= 0 && map[i][j - 1] > map[i][j] + 1){map[i][j - 1] = map[i][j] + 1;
                quque.push([i,j - 1])
            }
            if(j + 1 < map[0].length && map[i][j + 1] > map[i][j] + 1){map[i][j + 1] = map[i][j] + 1;
                quque.push([i,j + 1])
            }
        }

    }
    return map;
   };

不像其余的,这里是须要一开始就把所有的 0 地位放到 quque 中去当做一个汇合,与岛屿大小问题大同小异

退出移动版