jayati

Rotting Oranges

May 29th, 2024
711
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.46 KB | None | 0 0
  1. class Solution {
  2. public:
  3.     int orangesRotting(vector<vector<int>>& grid) {
  4.         queue<pair<pair<int,int>,int>> q;
  5.         int n=grid.size();
  6.         int m=grid[0].size();
  7.         int vis[n][m];
  8.         int cfresh=0;
  9.         for(int i=0;i<n;i++)
  10.         {
  11.             for(int j=0;j<m;j++)
  12.             {
  13.                 if(grid[i][j]==2)
  14.                 {
  15.                     q.push({{i,j},0});
  16.                     vis[i][j]=2;
  17.                 }
  18.                 else
  19.                 {
  20.                     vis[i][j]=0;
  21.                 }
  22.                 if(grid[i][j]==1)
  23.                 {
  24.                     cfresh++;
  25.                 }
  26.             }
  27.         }
  28.         int dx[4]={-1,0,1,0};
  29.         int dy[4]={0,1,0,-1};
  30.         int c=0;
  31.         int tm=0;
  32.         while(!q.empty())
  33.         {
  34.             int r=q.front().first.first;
  35.             int col=q.front().first.second;
  36.             int t=q.front().second;
  37.             tm = max(t,tm);
  38.             q.pop();
  39.             for(int k=0;k<4;k++)
  40.             {
  41.                 int nr=r+dx[k];
  42.                 int nc=col+dy[k];
  43.                
  44.                 if((nr>=0 && nr<n) && (nc>=0 && nc<m) && vis[nr][nc]==0 && grid[nr][nc]==1)
  45.                 {
  46.                     q.push({{nr,nc},t+1});
  47.                     vis[nr][nc]=2;
  48.                     c++;
  49.                 }
  50.             }
  51.         }
  52.         if(c!=cfresh)
  53.         {
  54.             return -1;
  55.         }
  56.         return tm;
  57.     }
  58. };
Advertisement
Add Comment
Please, Sign In to add comment