我对 "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;
}
}
在给定的网格中，每个单元格可以具有以下三个值之一：
值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;
}
}