text: 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.
  
  
  
  Example 1:
  
  
  
  Input: [[2,1,1],[1,1,0],[0,1,1]]
  Output: 4
  Example 2:
  
  Input: [[2,1,1],[0,1,1],[1,0,1]]
  Output: -1
  Explanation:  The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.
  Example 3:
  
  Input: [[0,2]]
  Output: 0
  Explanation:  Since there are already no fresh oranges at minute 0, the answer is just 0.
  
  
  Note:
  
  1 <= grid.length <= 10
  1 <= grid[0].length <= 10
  grid[i][j] is only 0, 1, or 2.
  
  
  
  
  
  
  
  
  
  class Solution {
  public:
  
      bool isValid(int x, int y, int m, int n){
          return (x>=0 && x<m && y>=0 && y<n);
      }
  
      int orangesRotting(vector<vector<int>>& grid) {
          int m=grid.size();
          if(!m) return -1;
          int n=grid[0].size();
  
          queue<pair<int, pair<int, int> > > q;  //  < time, < coord x, coord y > >
  
          for(int i=0; i<m;i++){
              for(int j=0;j<n;j++){
                  if(grid[i][j]==2){
                      q.push({0, {i, j}});
                  }
              }
          }
  
          pair<int, pair<int, int> > tmp;
  
          while(!q.empty()){
              tmp=q.front();
              q.pop();
              int i=tmp.second.first;
              int j=tmp.second.second;
  
              if(isValid(i-1, j, m, n) && grid[i-1][j]==1){ // top
                  grid[i-1][j]=2;
                  q.push({tmp.first+1, {i-1, j}});
              }
  
              if(isValid(i, j+1, m, n) && grid[i][j+1]==1){  // right
                  grid[i][j+1]=2;
                  q.push({tmp.first+1, {i, j+1}});
              }
  
              if(isValid(i+1, j, m, n) && grid[i+1][j]==1){  // down
                  grid[i+1][j]=2;
                  q.push({tmp.first+1, {i+1, j}});
              }
  
              if(isValid(i, j-1, m, n) && grid[i][j-1]==1){  // left
                  grid[i][j-1]=2;
                  q.push({tmp.first+1, {i, j-1}});
              }
          }
  
          int resultTime=tmp.first;
  
          for(int i=0;i<m;i++){
              for(int j=0;j<n;j++){
                  if(grid[i][j]==1){
                      resultTime=-1; break;
                  }
              }
          }
          return resultTime;
      }
  };
  