6.md

Distance of nearest cell having 1

vector<vector<int>>nearest(vector<vector<int>>grid)
	{
	    // Code here
	    
	    int n=grid.size();
	    int m=grid[0].size();
	    
	    vector<vector<int>> visited(n,vector<int>(m,0));
	    
	     vector<vector<int>>dist(n,vector<int>(m,0));
	     
	     queue<pair<pair<int,int>,int>>q;
	     
	     for(int i=0;i<n;i++)
	        for(int j=0;j<m;j++)
	            if(grid[i][j]==1)
	            {
	                visited[i][j]=1;
	                dist[i][j]=0;
	                q.push({{i,j},0});
	            }
	            
	      int drow[]={-1,0,1,0};
	      int dcol[]={0,1,0,-1};
	      
	      while(!q.empty())
	      {
	          int r=q.front().first.first;
	          int c=q.front().first.second;
	          
	          int t=q.front().second;
	          
	          q.pop();
	          
	          for(int i=0;i<4;i++)
	          {
	              int rt= r+drow[i];
	              int ct= c+dcol[i];
	              
	              if(rt>=0 && rt<n && ct>=0 && ct<m && visited[rt][ct]!=1 && grid[rt][ct]!=1)
	              {
	                  visited[rt][ct]=1;
	                  dist[rt][ct]=t+1;
	                  q.push({{rt,ct},t+1});
	              }
	          }
	      }
	      
	      return dist;
	}

0/1 MATRIX

vector<vector<int>> updateMatrix(vector<vector<int>>& grid) {
        
	    int n=grid.size();
	    int m=grid[0].size();
	    
	    vector<vector<int>> visited(n,vector<int>(m,0));
	    
	     vector<vector<int>>dist(n,vector<int>(m,0));
	     
	     queue<pair<pair<int,int>,int>>q;
	     
	     for(int i=0;i<n;i++)
	        for(int j=0;j<m;j++)
	            if(grid[i][j]==0)
	            {
	                visited[i][j]=1;
	                dist[i][j]=0;
	                q.push({{i,j},0});
	            }
	            
	      int drow[]={-1,0,1,0};
	      int dcol[]={0,1,0,-1};
	      
	      while(!q.empty())
	      {
	          int r=q.front().first.first;
	          int c=q.front().first.second;
	          
	          int t=q.front().second;
	          
	          q.pop();
	          
	          for(int i=0;i<4;i++)
	          {
	              int rt= r+drow[i];
	              int ct= c+dcol[i];
	              
	              if(rt>=0 && rt<n && ct>=0 && ct<m && visited[rt][ct]!=1 && grid[rt][ct]!=0)
	              {
	                  visited[rt][ct]=1;
	                  dist[rt][ct]=t+1;
	                  q.push({{rt,ct},t+1});
	              }
	          }
	      }
	      
	      return dist;
	}