Мое решение проблемы «Гнилые апельсины» дает неправильный результат. Я реализовал это с помощью BFS

Изменить 1

Ваш способ подсчета минут неверен, вы увеличиваете минуты каждый раз, когда гнилой апельсин меняет хотя бы свежий апельсин на гнилой. Из-за этого минута результата в минуту также зависит от порядка, в котором вы повторяете гнилой апельсин, это неправильно.

Апельсины должны портиться параллельно, порядок повторения в сетке не должен иметь значения.

Если я добавлю в вашу программу печать сетки в минуту, это даст:

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

Сравните с моими случаями

Редактировать 2

Исправленным способом из вашего предложения может быть:

#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;
}

Компиляция и исполнение:

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

t = 1
221
220
011

t = 2
222
220
022

2

Обратите внимание, что этот способ более эффективен, чем мой ниже, потому что вы учитываете только один раз каждый гнилой апельсин.

Необходимое время зависит от того, учитываются или не учитываются диагонали вокруг гнилого апельсина, чтобы свежий апельсин тоже стал гнилым.

Вот моя реализация, я использую переменную препроцессора ДИАГ, чтобы учитывать или не учитывать диагонали, и DEBUG, чтобы печатать или нет сетку каждую минуту:

#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;
}

Составление и исполнение с учетом диагоналей:

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

Составление и исполнение без учета диагоналей:

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

Это должно исправить это:

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;


    }
}