Rohit4Pal

Untitled

Aug 2nd, 2021
643
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2.     int m,n;
  3.     int row[4]={1,-1,0,0};
  4.     int col[4]={0,0,1,-1};
  5. public:
  6.     vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
  7.        
  8.         m=mat.size(),n=mat[0].size();
  9.         vector<vector<int>> res(m,vector<int>(n,-1));
  10.         vector<vector<bool>> visited(m,vector<bool>(n,false));
  11.        
  12.         for(int i=0;i<m;i++){
  13.             for(int j=0;j<n;j++){
  14.                
  15.                 if(mat[i][j]==0){
  16.                     res[i][j]=0;
  17.                     continue;
  18.                 }
  19.                 visited[i][j]=true;
  20.                 res[i][j]=disFromNearestZero(mat,i,j,res,visited);
  21.                 visited[i][j]=false;
  22.             }
  23.         }
  24.         return res;
  25.     }
  26.    
  27.     int disFromNearestZero(vector<vector<int>>& mat,int i,int j,vector<vector<int>> &res,vector<vector<bool>> &visited){
  28.        
  29.         //base case
  30.         if(mat[i][j]==0)    return 0;
  31.        
  32.         int minDis=INT_MAX-1;
  33.         for(int k=0;k<4;k++){
  34.            
  35.             int x=i+row[k],y=j+col[k];
  36.             if(isValid(x,y) && !visited[x][y]){
  37.                 visited[x][y]=true;
  38.                 minDis=min(minDis, 1+disFromNearestZero(mat,x,y,res,visited));
  39.                 visited[x][y]=false;
  40.             }
  41.         }
  42.         if(minDis==INT_MAX)     return minDis-1;              
  43.         return minDis;
  44.     }
  45.     bool isValid(int i,int j){
  46.         return i>=0 && j>=0 && i<m && j<n;
  47.     }
  48.     void print(vector<vector<int>> &res){
  49.        
  50.         for(auto &i:res){
  51.             for(int j:i)
  52.                 cout<<j<<" ";
  53.             cout<<"\n";
  54.         }
  55.     }
  56. };
RAW Paste Data