-
Notifications
You must be signed in to change notification settings - Fork 266
/
RottenOranges.cpp
92 lines (71 loc) · 2.31 KB
/
RottenOranges.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>
using namespace std;
/*
Problem Statement:
Given an m x n grid, where each cell has the following values:
2 – Rotten orange
1 – Fresh orange
0 – Empty cell
Every minute, if a Fresh orange is adjacent to a Rotten Orange in 4-direction
(upward, downwards, right, and left) it becomes Rotten.
Return the minimum number of minutes required such that
none of the cells has a Fresh Orange.
If it's not possible, return -1.
*/
// Approach: BFS
bool isValid(int nx, int ny, int m, int n) {
return (0 <= nx && nx < m) && (0 <= ny && ny < n);
}
// Time: O(mn) x 4
// Space: O(mn)
int orangesRotting(vector<vector<int>> &grid) {
int m = grid.size();
int n = grid[0].size();
int total = 0; // fresh + rotten oranges
int count = 0; // rotten oranges
int mins = 0; // minutes elapsed
queue<pair<int, int>> rotten; // {i, j}: position of rotten orange
// Count the fresh & rotten oranges, push rotten oranges into queue
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] != 0) // Rotten or Fresh orange
total++;
if (grid[i][j] == 2) // Rotten
rotten.push({i, j}); // Push position of rotten orange
}
}
int dx[] = {0, 0, -1, 1}; // 4-directions (x-axis)
int dy[] = {-1, 1, 0, 0}; // 4-directions (y-axis)
while (!rotten.empty()) {
int size = rotten.size(); // rotten oranges in current minute
count += size; // add to total rotten oranges
while (size--) // Each rotten orange in current minute
{
// Pop the front rotten orange
int x = rotten.front().first;
int y = rotten.front().second;
rotten.pop();
// Check for fresh oranges in 4-directions
for (int i = 0; i < 4; i++) {
// New coordinates
int nx = x + dx[i];
int ny = y + dy[i];
// Valid, fresh orange
if (isValid(nx, ny, m, n) && grid[nx][ny] == 1) {
grid[nx][ny] = 2; // make it rotten
rotten.push({nx, ny}); // push it into queue
}
}
}
if (!rotten.empty()) // if there are more rotten oranges
mins++;
}
if (total != count) // fresh oranges left
return -1;
return mins;
}
int main() {
vector<vector<int>> grid = {{2, 1, 1}, {1, 1, 0}, {0, 1, 1}};
cout << orangesRotting(grid) << endl; // 4
return 0;
}