01 Matrix解题报告-白红宇的个人博客

01 Matrix解题报告

发布日期：2022-02-25 00:55:20 浏览次数：41 分类：技术文章

本文共 1418 字，大约阅读时间需要 4 分钟。

这是一道中等题，题目链接为：

题目描述:现有一个只包含0和1的矩阵，找出每个元素最近的0的距离，并以矩阵的形式输出相邻的元素之间的距离为1，相邻指的是上下左右，不包括对角线样例1input:0 0 00 1 00 0 0output:0 0 00 1 00 0 0样例二:input:0 0 00 1 01 1 1output:0 0 00 1 01 2 1

首先元素为0时，它对应的距离是0，与0相邻的1的距离值是1，不同的距离值之间可以形成一种层次关系，距离值为0的是第0层，距离值为1的是第1层，以此类推，并且对于层次为n(n>0)的元素，必定只与层次为n-1或n+1的元素相邻，于是，对于这道题，可以用BFS算法从第0层开始一层一层地往较高层遍历。

算法的步骤如下:

step1:首先设置一个空队列q,所有位置(i,j)的访问状态visit[i][j]为false,并且对应距离值d[i][j]为0step2:所有为0的元素距离值为0，在第0层，将这些元素的位置(i,j)全部加入队列q中，同时设置访问状态visit[i][j]为true,距离d[i][j]为0step3:只要队列非空，从队列头取出一个位置(i,j),检查所有相邻位置(i',j')的访问状态，如果为false,则该相邻位置的距离值d[i'][j'] = d[i][j] + 1，访问状态设为true,并将位置(i',j')加入队列q,重复步骤3，若队列空了，就结束，并返回矩阵d

c++代码如下:

class Solution {private:    vector
   
    
     >visit,d;    queue
     
      
       >q;    pair
       
        p;    int cur_i,cur_j;    int width,height;    void push_and_set(int row,int col){        if(row>=0&&row
        
         =0&&col

> updateMatrix(vector

>& matrix) { height = matrix.size(); width = matrix[0].size(); visit = vector

>(height,vector

(width)); d = vector

>(height,vector

(width)); for(int i = 0; i < height; i++){ for(int j = 0; j < width; j++){ if(matrix[i][j] == 0){ q.push(make_pair(i,j)); visit[i][j]=1; d[i][j] = 0; } } } while(!q.empty()){ p = q.front(); q.pop(); cur_i = p.first; cur_j = p.second; push_and_set(cur_i - 1, cur_j); push_and_set(cur_i + 1, cur_j); push_and_set(cur_i, cur_j + 1); push_and_set(cur_i, cur_j - 1); } return d; }};

转载地址：https://blog.csdn.net/qq_30306087/article/details/78085606 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：Number of Longest Increasing Subsequence 解题报告

下一篇：Longest Valid Parentheses

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章