My solution of "Rotten Oranges" problem gives incorrect output. I've implemented it using BFS

Question

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.

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int m,n;
       m = grid.size();
        n = grid[0].size();

        int i, j, min = 0,flag=0,fresh=0;

        int r[4] = {-1,1,0,0};
        int c[4] = {0,0,-1,1};
        for(i=0;i<m;i++) {
            for(j=0;j<n;j++) {
                if(grid[i][j]==1) 
                    fresh++;
            }
        }
        queue< pair<int, int> >q;
        for(i=0;i<m;i++) {
            for(j=0;j<n;j++) {
                if(grid[i][j] == 2) {
                    q.push(make_pair(i,j));
                    flag=1;
                    break;
                }
            }
            if(flag==1)
                break;  
        }
        while(!q.empty()) {

            pair<int,int> p = q.front();
            int a = p.first;
            int b = p.second;
          int x=0;
            q.pop();
            for(i=0;i<4;i++) {
                for(j=0;j<4;j++) {
                    int rr = a + r[i];
                    int cc = b + c[j];
                    if(rr<0 || cc<0 || rr>=m || cc>=n || grid[rr][cc]==0 || grid[rr][cc] ==2) {
                        continue;
                    }
                    else if(grid[rr][cc] ==1) {
                         grid[rr][cc] =2;
                        q.push(make_pair(rr,cc));
                        fresh--;  
                        x++;
                    }     
                }
            }    
     if(x>0) min++;
        } 
     return fresh >0 ? -1:min; 
    }
};

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

Output: 3

Expected: 4

Answer 1

This should fix it:

public class Orange
{
    public int TimeFrame,x,y;
    public Orange(int x, int y, int timeFrame)
    {
        this.x = x;
        this.y = y;
        this.TimeFrame = timeFrame;

    }
    
}
internal class RottenOrange
{
    Queue<Orange> queue = new Queue<Orange>();
    int timeFrame = 0;

    public int OrangesRotting(int[][] grid)
    {
        
        FindRottenOrange(grid,true);
        while(queue.Count>0)
        {
            var dequeue = queue.Dequeue();
            // check left
            if( dequeue.y>0)
            {
                if (grid[dequeue.x][dequeue.y - 1] == 1)
                {
                    grid[dequeue.x][dequeue.y - 1] = 2;
                    queue.Enqueue(new Orange(dequeue.x, dequeue.y - 1, dequeue.TimeFrame + 1));
                    timeFrame = dequeue.TimeFrame + 1;
                }
            }
            // check right
            if (dequeue.y < grid[dequeue.x].Length-1)
            {
                if (grid[dequeue.x][dequeue.y+1] == 1)
                {
                    grid[dequeue.x][dequeue.y + 1] = 2;
                       queue.Enqueue(new Orange(dequeue.x, dequeue.y+1, dequeue.TimeFrame + 1));
                    timeFrame = dequeue.TimeFrame + 1;
                }
                

            }
            // check up
            if (dequeue.x >0)
            {
                if (grid[dequeue.x - 1][dequeue.y] == 1)
                {
                    grid[dequeue.x - 1][dequeue.y] = 2;
                    queue.Enqueue(new Orange(dequeue.x - 1, dequeue.y, dequeue.TimeFrame + 1));
                    timeFrame = dequeue.TimeFrame + 1;
                }

            }
            // check down
            if (dequeue.x < grid.Length-1)
            {
                if (grid[dequeue.x+1][dequeue.y] == 1)
                {
                    grid[dequeue.x + 1][dequeue.y] = 2;
                    queue.Enqueue(new Orange(dequeue.x+1, dequeue.y, dequeue.TimeFrame + 1));
                    timeFrame = dequeue.TimeFrame + 1;
                }

            }

        }
        FindRottenOrange(grid,false);
        if(queue.Count>0)
        {
            timeFrame = -1;
        }
        return timeFrame;
    }
    private Queue<Orange> FindRottenOrange(int[][] grid,bool isRotten)
    {

        for (int i = 0; i < grid.Length; i++)
        {
            for (int j = 0; j < grid[i].Length; j++)
            {
                if (isRotten && grid[i][j] == 2)
                {
                    queue.Enqueue(new Orange(i, j, timeFrame));
                }
                else if(!isRotten && grid[i][j] == 1)
                {
                    queue.Enqueue(new Orange(i, j, timeFrame));
                }
            }
        }

        return queue;


    }
}

Answer 2

Edit 1

Your way to count the minutes is wrong, you increment the minutes each time a rotten orange changes at least a fresh orange to a rotten one. Because of that the result minute per minute also depends on the order you iterate on the rotten orange, this is wrong.

The oranges must become rotten in parallel, the order you iterate into the grid must not be relevant.

If I add in your program the print of the grid per minute that gives :

t = 0
211
110
011

t = 1
221
220
011

t = 2
221
220
021

t = 3
222
220
022

t = 3
222
220
022

t = 3
222
220
022

t = 3
222
220
022

Compare with my cases

---

Edit 2

A corrected way from your proposal can be :

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int orangesRotting(vector<vector<int>>& grid) {
  int m,n;
  m = grid.size();
  n = grid[0].size();

  int i, j, min = 0,flag=0,fresh=0;

  int r[4] = {-1,1,0,0};
  int c[4] = {0,0,-1,1};

  queue< pair<int, int>>q;

  for(i=0;i<m;i++) {
    for(j=0;j<n;j++) {
      if (grid[i][j] == 1)
        fresh++;
      else if (grid[i][j] == 2)
        q.push(make_pair(i,j));
    }
  }

  if (fresh == 0)
    return 0;

  if (q.empty())
    return -1;

  for (;;) {
#ifdef DEBUG
    cout << "t = " << min << endl;
    for(i=0;i<m;i++) {
      for(j=0;j<n;j++)
        cout << grid[i][j];
      cout << endl;
    }
    cout << endl;
#endif
    queue< pair<int, int>>qnext;
    while (!q.empty()) {
      pair<int,int> p = q.front();
      int a = p.first;
      int b = p.second;
      q.pop();
      for(i=0;i<4;i++) {
        for(j=0;j<4;j++) {
          int rr = a + r[i];
          int cc = b + c[j];

          if (!(rr<0 || cc<0 || rr>=m || cc>=n || grid[rr][cc]==0 || grid[rr][cc] ==2)
              && (grid[rr][cc] ==1)) {
            grid[rr][cc] = 2;
            qnext.push(make_pair(rr,cc));
            fresh--;  
          }     
        }
      }    
    }
    min += 1;
    if (fresh == 0) {
#ifdef DEBUG
      cout << "t = " << min << endl;
      for(i=0;i<m;i++) {
        for(j=0;j<n;j++)
          cout << grid[i][j];
        cout << endl;
      }
      cout << endl;
#endif   
      return min;
    }
    if (qnext.empty())
      return -1;
    q = qnext;
  } 
}

int main()
{
  vector<vector<int> > grid;

  grid.resize(3);

  grid[0].push_back(2);
  grid[0].push_back(1);
  grid[0].push_back(1);

  grid[1].push_back(1);
  grid[1].push_back(1);
  grid[1].push_back(0);

  grid[2].push_back(0);
  grid[2].push_back(1);
  grid[2].push_back(1);

  cout << orangesRotting(grid) << endl;
}

Compilation and execution :

/tmp % g++ -DDEBUG oo.cc
/tmp % ./a.out
t = 0
211
110
011

t = 1
221
220
011

t = 2
222
220
022

2

Note that way is more efficient than mine below because you consider only one time each rotten orange

---

The needed time depends on the fact the diagonals are or not taken into account around a rotten orange to make the fresh orange rotten too.

Here my implementation, I use the preprocessor variable DIAG to take into account or not the diagonals, and DEBUG to print or not the grid each minutes :

#include <iostream>
#include <vector>

using namespace std;

enum State { Empty, Fresh, Rotten };

// I do not see the interest of the class so I removed it
// I do not want to modify the input vector so I get it by value

int orangesRotting(vector<vector<State>> grid)
{
  int nmins = 0;
  const size_t height = grid.size();

  if (height == 0)
    return -1;

  const size_t width = grid[0].size(); // suppose same size for all sub vectors

  if (width == 0)
    return -1;

  // the grid for the next min, do not work on the
  // current grid to not see the cells becoming rotten
  // in the current step, changes are done simultaneously
  vector<vector<State>> nextGrid = grid;

  for (;;) {
#ifdef DEBUG
    cout << "t = " << nmins << endl;
#endif

    bool modified = false;
    int nWasFresh = 0;

    for (size_t i = 0; i != height; ++i) {
      vector<State> & v = grid[i];

      for (size_t j = 0; j != width; ++j) {
#ifdef DEBUG
        cout << v[j];
#endif
        switch (v[j]) {
        case Rotten: 
          {
            // make fresh cells around rotten
#ifdef DIAG
            const size_t maxh = min(i + 1, height - 1);
            const size_t minw = (j == 0) ? j : j - 1;
            const size_t maxw = min(j + 1, width - 1);

            for (size_t a = (i == 0) ? i : i - 1; a <= maxh; ++a) {
              vector<State> & v = grid[a];

              for (size_t b = minw; b <= maxw; ++b) {
                if (v[b] == Fresh) {
                  modified = true;
                  nextGrid[a][b] = Rotten;
                }
              }
            }
#else
            if ((i != 0) && (grid[i-1][j] == Fresh)) {
              modified = true;
              nextGrid[i-1][j] = Rotten;
            }
            if ((i != (height-1)) && (grid[i+1][j] == Fresh)) {
              modified = true;
              nextGrid[i+1][j] = Rotten;
            }
            if ((j != 0) && (grid[i][j-1] == Fresh)) {
              modified = true;
              nextGrid[i][j-1] = Rotten;
            }
            if ((j != (width-1)) && (grid[i][j+1] == Fresh)) {
              modified = true;
              nextGrid[i][j+1] = Rotten;
            }
#endif
          }
          break;
        case Fresh:
          nWasFresh += 1;
          break;
        default:
          break;
        }
      }
#ifdef DEBUG
      cout << endl;
#endif
    }
#ifdef DEBUG
    cout << endl;
#endif

    if (nWasFresh == 0)
      return nmins;

    if (!modified)
      return -1;

    // update grid and time
    grid = nextGrid;
    nmins += 1;
  }
}

int main()
{
  vector<vector<State>> grid;

  grid.resize(3);

  grid[0].push_back(Rotten);
  grid[0].push_back(Fresh);
  grid[0].push_back(Fresh);

  grid[1].push_back(Fresh);
  grid[1].push_back(Fresh);
  grid[1].push_back(Empty);

  grid[2].push_back(Empty);
  grid[2].push_back(Fresh);
  grid[2].push_back(Fresh);

  cout << orangesRotting(grid) << endl;
}

Compilation and execution taking into account the diagonals :

pi@raspberrypi:/tmp $ g++ -DDEBUG -DDIAG -pedantic -Wextra -Wall o.cc
pi@raspberrypi:/tmp $ ./a.out
t = 0
211
110
011

t = 1
221
220
011

t = 2
222
220
022

2

Compilation and execution without taking into account the diagonals :

pi@raspberrypi:/tmp $ g++ -DDEBUG -pedantic -Wextra -Wall o.cc
pi@raspberrypi:/tmp $ ./a.out
t = 0
211
110
011

t = 1
221
210
011

t = 2
222
220
011

t = 3
222
220
021

t = 4
222
220
022

4