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