994. Rotting Oranges
1. Description
You are given an m x n grid where each cell can have one of three values:
- 0 representing an empty cell,
- 1 representing a fresh orange, or
- 2 representing a rotten orange.
Every minute, any fresh orange that is 4-directionally adjacent 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.
2. Example
Example 1:
Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Example 2:
Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.
Example 3:
Input: grid = [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.
3. Constraints
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 10
- grid[i][j] is 0, 1, or 2.
4. Solutions
Breadth-First Search
n is the number of elements in root
Time complexity: O(n)
Space complexity: O(n)
class Solution {
public:
int orangesRotting(vector<vector<int>> grid) {
queue<pair<int, int>> rot_orange;
queue<pair<int, int>> orange_to_rot;
int fresh_orange = 0;
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[i].size(); ++j) {
if (grid[i][j] == 1) {
++fresh_orange;
} else if (grid[i][j] == 2) {
rot_orange.push({i, j});
}
}
}
if (fresh_orange == 0) {
return 0;
}
if (rot_orange.empty()) {
return -1;
}
int minute = 0;
while (!rot_orange.empty()) {
while (!rot_orange.empty()) {
auto position = rot_orange.front();
rot_orange.pop();
traverse_({position.first + 1, position.second}, grid, orange_to_rot, fresh_orange);
traverse_({position.first - 1, position.second}, grid, orange_to_rot, fresh_orange);
traverse_({position.first, position.second + 1}, grid, orange_to_rot, fresh_orange);
traverse_({position.first, position.second - 1}, grid, orange_to_rot, fresh_orange);
}
++minute;
rot_orange = move(orange_to_rot);
}
return fresh_orange == 0 ? minute - 1 : -1;
}
private:
void traverse_(
pair<int, int> position,
vector<vector<int>> &grid,
queue<pair<int, int>> &orange_to_rot,
int &fresh_orange) {
if (0 <= position.first && position.first < grid.size() && 0 <= position.second &&
position.second < grid[0].size()) {
if (grid[position.first][position.second] == 1) {
grid[position.first][position.second] = 2;
--fresh_orange;
orange_to_rot.push({position.first, position.second});
}
}
}
};