Leetcode 542, 01 matrix

542、01 matrix

1） Title Description

Given a by 0 and 1 Matrix of composition mat , Please output a matrix of the same size , Each of these grids is mat From the corresponding position element to the nearest 0 Distance of .

The distance between two adjacent elements is 1 .

Example 1：

 Input ：mat = [[0,0,0],[0,1,0],[0,0,0]]
 Output ：[[0,0,0],[0,1,0],[0,0,0]]

Example 2：

 Input ：mat = [[0,0,0],[0,1,0],[1,1,1]]
 Output ：[[0,0,0],[0,1,0],[1,2,1]]

Tips ：

• 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 At least one of them 0

2） analysis

Breadth first search .

Store all 0 The location of , The team , Then traverse the queue , If there are around 1 , Then set the number of steps , Then add it to the queue .

3）C++ Code

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};

        // Access all zeros and put 0 Join the queue 
        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;
                }
            }
        }

        // Breadth first search 
        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;
    }
};