Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution
- {
- public:
- //Function to find minimum time required to rot all oranges.
- int orangesRotting(vector<vector<int>>& grid) {
- deque<pair<int,int>> q;
- int row=grid.size(),col=grid[0].size();
- vector<vector<bool>> check(row,vector<bool>(col,false));
- int total_fresh=0,ans=0;
- for(int i=0;i<row;i++){
- for(int j=0;j<col;j++){
- if(grid[i][j]==2){ q.push_back(make_pair(i,j)); check[i][j]=true;}
- if(grid[i][j]==1) total_fresh++;
- }
- }
- while(q.size() && total_fresh){
- int k=q.size();
- int x[4]={-1,0,1,0};
- int y[4]={0,1,0,-1};
- for(int i=0;i<k;i++){
- pair<int,int> temp=q.front();
- q.pop_front();
- for(int k=0;k<4;k++){
- int new_x=temp.first+x[k];
- int new_y=temp.second+y[k];
- if(new_x>=0 && new_y>=0 && new_x<row && new_y<col && grid[new_x][new_y]==1 && !check[new_x][new_y]){
- q.push_back(make_pair(new_x,new_y));
- check[new_x][new_y]=true;
- total_fresh--;
- }
- }
- }
- ans++;
- }
- if(total_fresh!=0) return -1;
- return ans;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement