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.
rotting-oranges-puzzle-using-bfs-algorithm
Input: [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Example 2:Input: [[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: [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.Note:
1 <= grid.length <= 10
1 <= grid[0].length <= 10
grid[i][j] is only 0, 1, or 2.
Breadth-First Search Algorithm to Solve Puzzle in a Grid
The Breadth First Search algorithm can be applied to multiple roots – which all indicate the same level. Thus, we push the initial rotten oranges into the queue – with minute equals to zero. When the queue is not empty, we pop up a node in the front of the queue, make a new node (its children with minute plus one and updated location), if the location is valid, it has a rotten orange on the cell, we increment the counter and push the child node to the queue.
The following C++ implements the Breadth First Search Algorithm, and tuples that consist of X, Y and minutes are pushed to the queue.
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 | class Solution { public: int orangesRotting(vector<vector<int>>& grid) { int row = grid.size(); if (row == 0) return 0; int col = grid[0].size(); int total = 0; queue<tuple<int, int, int>> Q; for (int i = 0; i < row; ++ i) { for (int j = 0; j < col; ++ j) { if (grid[i][j] == 2) { // push the initial rotten oranges to the queue Q.push(make_tuple(i, j, 0)); } else if (grid[i][j] == 1) { total ++; // fresh count } } } int step = 0, cnt = 0; // count to make a fresh rotten while (!Q.empty()) { auto p = Q.front(); Q.pop(); int r = std::get<0>(p); int c = std::get<1>(p); int s = std::get<2>(p); step = max(step, s); if ((r > 0) && (grid[r - 1][c] == 1)) { Q.push(make_tuple(r - 1, c, s + 1)); grid[r - 1][c] = 2; cnt ++; } if ((c > 0) && (grid[r][c - 1] == 1)) { Q.push(make_tuple(r, c - 1, s + 1)); grid[r][c - 1] = 2; cnt ++; } if ((r + 1 < row) && (grid[r + 1][c] == 1)) { Q.push(make_tuple(r + 1, c, s + 1)); grid[r + 1][c] = 2; cnt ++; } if ((c + 1 < col) && (grid[r][c + 1] == 1)) { Q.push(make_tuple(r, c + 1, s + 1)); grid[r][c + 1] = 2; cnt ++; } } return cnt == total ? step : -1; } }; |
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
int row = grid.size();
if (row == 0) return 0;
int col = grid[0].size();
int total = 0;
queue<tuple<int, int, int>> Q;
for (int i = 0; i < row; ++ i) {
for (int j = 0; j < col; ++ j) {
if (grid[i][j] == 2) {
// push the initial rotten oranges to the queue
Q.push(make_tuple(i, j, 0));
} else if (grid[i][j] == 1) {
total ++; // fresh count
}
}
}
int step = 0, cnt = 0; // count to make a fresh rotten
while (!Q.empty()) {
auto p = Q.front();
Q.pop();
int r = std::get<0>(p);
int c = std::get<1>(p);
int s = std::get<2>(p);
step = max(step, s);
if ((r > 0) && (grid[r - 1][c] == 1)) {
Q.push(make_tuple(r - 1, c, s + 1));
grid[r - 1][c] = 2;
cnt ++;
}
if ((c > 0) && (grid[r][c - 1] == 1)) {
Q.push(make_tuple(r, c - 1, s + 1));
grid[r][c - 1] = 2;
cnt ++;
}
if ((r + 1 < row) && (grid[r + 1][c] == 1)) {
Q.push(make_tuple(r + 1, c, s + 1));
grid[r + 1][c] = 2;
cnt ++;
}
if ((c + 1 < col) && (grid[r][c + 1] == 1)) {
Q.push(make_tuple(r, c + 1, s + 1));
grid[r][c + 1] = 2;
cnt ++;
}
}
return cnt == total ? step : -1;
}
};The time complexity is O(N) where N is the number of the cells in the grid, and the space complexity is also O(N).
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Facebook Onsite Interview Preparation Part 1: Motivation/Bahavior Questions
Next Post: The Process Killing Algorithms using Depth First Search or Breadth First Search (Kill a Process)
