Untitled
unknown
plain_text
a year ago
1.6 kB
2
Indexable
Never
class Solution { public: void rot(vector<vector<int>>& grid,int x,int y,int r,int c,queue<pair<int,int>>&q){ if(x-1>=0 && grid[x-1][y]==1) {grid[x-1][y]=2; q.push({x-1,y});} if(x+1<r && grid[x+1][y]==1) {grid[x+1][y]=2; q.push({x+1,y});} if(y+1<c && grid[x][y+1]==1) {grid[x][y+1]=2; q.push({x,y+1});} if(y-1>=0 && grid[x][y-1]==1) {grid[x][y-1]=2; q.push({x,y-1});} //fresh=false; //if((x-1<0 || grid[x-1][y]==0 ) && (x+1>=r || grid[x+1][y]==0) && (y-1<0 || grid[x][y-1]==0) && (y+1>=c || grid[x][y+1]==0)) fresh =true; } int orangesRotting(vector<vector<int>>& grid) { int r=grid.size(), c=grid[0].size(); if(r==1 && c==1) { if(grid[0][0]==1) return -1; return 0; } queue<pair<int,int>> q; //holds rotten oragnes coordinates int time=0; for(int i=0;i<r;i++){ for(int j=0;j<c;j++){ if(grid[i][j]==2) q.push({i,j}); } } while(!q.empty()){ int s=q.size(); while(s--){ //process one time period pair<int,int> p =q.front(); q.pop(); int x=p.first, y=p.second; //bool fresh =false; rot(grid,x,y,r,c,q); } time++; } for(int i=0;i<r;i++){ for(int j=0;j<c;j++){ if(grid[i][j]==1) return -1; } } if(time>0) return time-1; else return 0; } };