01-matrix

matrix01.cc

class Solution {
public:  
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        int n = matrix.size();
        int m = 0;
        if(n>0) m = matrix[0].size();        
        int max_dist = 100000;                
        queue< pair<int, int> > q;
                                 
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(matrix[i][j] == 0) {                                        
                    q.push(make_pair(i,j));
                }
                else{
                    matrix[i][j] = max_dist;
                }
            }
        }
                                 
        vector< vector <int> > dir = {{0,1},{0,-1},{1,0},{-1,0}};
        while(!q.empty()){
            pair<int, int> p = q.front();
            q.pop();
            int x = p.first;
            int y = p.second;
            for(const auto &it : dir){
                int xx = x + it[0];
                int yy = y + it[1];
                if(xx>=0 && xx<n && yy>=0 && yy<m){                    
                    if(matrix[xx][yy] > matrix[x][y] + 1) {
                        matrix[xx][yy] = matrix[x][y] + 1;                            
                        q.push(make_pair(xx,yy));
                    }                    
                }
            }
        }
        return matrix;
    }
};