Редактировать 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