Advertisement
imashutosh51

Rotten oranges

Jul 23rd, 2022 (edited)
48
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.35 KB | None | 0 0
  1. class Solution
  2. {
  3.     public:
  4.     //Function to find minimum time required to rot all oranges.
  5.     int orangesRotting(vector<vector<int>>& grid) {
  6.         deque<pair<int,int>> q;
  7.         int row=grid.size(),col=grid[0].size();
  8.         vector<vector<bool>> check(row,vector<bool>(col,false));
  9.         int total_fresh=0,ans=0;
  10.         for(int i=0;i<row;i++){
  11.             for(int j=0;j<col;j++){
  12.                 if(grid[i][j]==2){ q.push_back(make_pair(i,j)); check[i][j]=true;}
  13.                 if(grid[i][j]==1) total_fresh++;
  14.             }
  15.         }
  16.         while(q.size() && total_fresh){
  17.             int k=q.size();
  18.             int x[4]={-1,0,1,0};
  19.             int y[4]={0,1,0,-1};
  20.             for(int i=0;i<k;i++){
  21.                 pair<int,int> temp=q.front();
  22.                 q.pop_front();
  23.                 for(int k=0;k<4;k++){
  24.                     int new_x=temp.first+x[k];
  25.                     int new_y=temp.second+y[k];
  26.                     if(new_x>=0 && new_y>=0 && new_x<row && new_y<col && grid[new_x][new_y]==1 && !check[new_x][new_y]){
  27.                         q.push_back(make_pair(new_x,new_y));
  28.                         check[new_x][new_y]=true;
  29.                         total_fresh--;
  30.                     }
  31.                 }
  32.             }
  33.             ans++;
  34.         }
  35.         if(total_fresh!=0) return -1;
  36.         return ans;
  37.     }
  38. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement