Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public:
- int orangesRotting(vector<vector<int>>& grid) {
- queue<pair<pair<int,int>,int>> q;
- int n=grid.size();
- int m=grid[0].size();
- int vis[n][m];
- int cfresh=0;
- for(int i=0;i<n;i++)
- {
- for(int j=0;j<m;j++)
- {
- if(grid[i][j]==2)
- {
- q.push({{i,j},0});
- vis[i][j]=2;
- }
- else
- {
- vis[i][j]=0;
- }
- if(grid[i][j]==1)
- {
- cfresh++;
- }
- }
- }
- int dx[4]={-1,0,1,0};
- int dy[4]={0,1,0,-1};
- int c=0;
- int tm=0;
- while(!q.empty())
- {
- int r=q.front().first.first;
- int col=q.front().first.second;
- int t=q.front().second;
- tm = max(t,tm);
- q.pop();
- for(int k=0;k<4;k++)
- {
- int nr=r+dx[k];
- int nc=col+dy[k];
- if((nr>=0 && nr<n) && (nc>=0 && nc<m) && vis[nr][nc]==0 && grid[nr][nc]==1)
- {
- q.push({{nr,nc},t+1});
- vis[nr][nc]=2;
- c++;
- }
- }
- }
- if(c!=cfresh)
- {
- return -1;
- }
- return tm;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment