Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.6 kB
3
Indexable
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;
    }
};