Rotting Oranges

 

 Rotting Oranges

In a given grid, each cell can have one of three values:

• the value 0 representing an empty cell;
• the value 1 representing a fresh orange;
• the value 2 representing a rotten orange.

Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange.  If this is impossible, return -1 instead.

 

Input: [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Input: [[2,1,1],[0,1,1],[1,0,1]]
Output: -1 

Input: [[0,2]]
Output: 0

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
         queue< pair<int,int> > q;
        int n=grid.size(),m=grid[0].size();
        for(int i=0;i<grid.size();++i)
        {
            for(int j=0;j<grid[i].size();++j)
            {
                if(grid[i][j]==2)
                {
                q.push(make_pair(i,j));
                }
            }
        }
        int cnt=0;
        vector<pair<int,int> > v{{0,-1},{-1,0},{0,1},{1,0}};
       
        while(q.size()>0)
        {
            int s=q.size();
            int f=1;
            while(s--)
            {
                auto p=q.front();
                q.pop();
                int i=p.first;
                int j=p.second;
                 for(auto k: v)
                 {
                     int x=i+k.first;
                     int y=j+k.second;
                     if(x>=0&&x<n&&y>=0&&y<m&&grid[x][y]==1)
                     {
                         grid[x][y]=2;
                         q.push(make_pair(x,y));
                         if(f){
                             ++cnt;
                             f=0;
                         }
                     }
                 }
             }
           
        }
       
        int l=0;
       
         for(int i=0;i<grid.size();++i)
         {
            for(int j=0;j<grid[i].size();++j)
            {
                if(grid[i][j]==1)
                {
                 l=1;
                    break;
                }
            }
             if(l)break;
         }
        if(l)
            return -1;
        else
            return cnt;
       
    }
};