Leetcode542:矩阵(广度遍历解法)

举报
伯约同学 发表于 2022/03/09 22:08:26 2022/03/09
【摘要】 给定一个由 0 和 1 组成的矩阵 mat ,请输出一个大小相同的矩阵,其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。两个相邻元素间的距离为 1 。答题/**​ * @param {number[][]} mat​ * @return {number[][]} */ var updateMatrix = function(mat) { let map = new ...

给定一个由 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中去当做一个集合,与岛屿大小问题大同小异

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。