当前位置：网站首页>LeetCode 542、01 矩阵

LeetCode 542、01 矩阵

2022-04-23 20:23:00 【亡于灬】

542、01 矩阵

1）题目描述

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

示例 1：

img

输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
输出：[[0,0,0],[0,1,0],[0,0,0]]

示例 2：

img

输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
输出：[[0,0,0],[0,1,0],[1,2,1]]

提示：

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 10^4
  • 1 <= m * n <= 10^4
  • mat[i][j] is either 0 or 1.
  • mat 中至少有一个 0

2）分析

广度优先搜索。

存储所有 0 的位置，入队，然后遍历队列，如果四周存在 1 ，那么设置步数，然后添加进队列。

3）C++代码

class Solution {
    
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
    
        int m=mat.size();
        int n=mat[0].size();
        vector<vector<int>> seen(m,vector<int> (n,0));
        vector<vector<int>> distance(m,vector<int> (n,0));
        queue<pair<int,int>> que;
        int dx[4]={
    1,0,-1,0};
        int dy[4]={
    0,1,0,-1};

        //访问所有的零并将0加入队列
        for(int i=0;i<m;i++){
    
            for(int j=0;j<n;j++){
    
                if(!mat[i][j]){
    
                    que.emplace(i,j);
                    seen[i][j]=1;
                }
            }
        }

        //广度优先搜索
        while(!que.empty()){
    
            int x=que.front().first;
            int y=que.front().second;
            que.pop();
            for(int i=0;i<4;i++){
    
                int newX=x+dx[i];
                int newY=y+dy[i];
                if(newX>=0&&newX<m&&newY>=0&&newY<n&&!seen[newX][newY]){
    
                    seen[newX][newY]=1;
                    distance[newX][newY]=distance[x][y]+1;
                    que.emplace(newX,newY);
                }
            }
        }
        return distance;
    }
};

版权声明
本文为[亡于灬]所创，转载请带上原文链接，感谢
https://blog.csdn.net/qq_38342510/article/details/124360368

边栏推荐

猜你喜欢

随机推荐