01 matrix DP

matrix01DP.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;  
        vector< vector<int> > dist(n, vector<int> (m, max_dist));
                                 
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(!matrix[i][j]) dist[i][j] = 0;
                else{
                    if(i > 0) dist[i][j] = min(dist[i-1][j]+1, dist[i][j]);
                    if(j > 0) dist[i][j] = min(dist[i][j-1]+1, dist[i][j]);
                }
            }
        }
        
        for(int i = n-1; i >= 0; i--){
            for(int j = m-1; j >= 0; j--){
                if(!matrix[i][j]) dist[i][j] = 0;
                else{
                    if(i<n-1) dist[i][j] = min(dist[i+1][j]+1, dist[i][j]);
                    if(j<m-1) dist[i][j] = min(dist[i][j+1]+1, dist[i][j]);
                }        
            }
        }              
                                         
        return dist;
    }
};