我对 "Rotten Oranges" 问题的解决方案给出了错误的输出。我已经使用 BFS 实现了它

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

在给定的网格中,每个单元格可以具有以下三个值之一:

值0表示空单元格; 值 1 代表一个新鲜的橙子; 值 2 代表烂橙子。 每分钟,任何与腐烂的橘子相邻(4 向)的新鲜橘子都会腐烂。

Return 在没有单元格有新鲜橙色之前必须经过的最小分钟数。如果这不可能,则改为 return -1。

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

输入:[[2,1,1],[1,1,0],[0,1,1]]

输出:3

预期:4

编辑 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

注意这个方法比下面我的方法更有效,因为你只考虑每个烂橙子一次


所需的时间取决于是否考虑到烂橙子周围的对角线以使新鲜橙子也烂掉。

在我的实现中,我使用预处理器变量 DIAG 来考虑或不考虑对角线,并使用 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;


    }
}