LeetCode 542、01 矩阵

542、01 矩阵

1）题目描述

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

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

示例 1：

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

示例 2：

输入：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;
    }
};