题目描述
题目链接:994. Rotting Oranges
In a given grid, each cell can have one of three values:
the value
0
representing an empty cell; the value1
representing a fresh orange; the value2
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.
例子
例子 1
Input:
[[2,1,1],[1,1,0],[0,1,1]]
Output: 4
例子 2
Input:
[[2,1,1],[0,1,1],[1,0,1]]
Output: -1 Explaination:The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.
例子 3
Input:
[[0,2]]
Output: 0 Explaination: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 only0
,1
, or2
.
解题思路
方法一
通过找最短时间,问题可以转化问对每一个新鲜橙子,找离它最近的发霉橙子;这样就变成了一个搜索问题,而按找最近的思路,很明显应该应该用 bfs,我一开始想了一个不太直观而且比较麻烦的方法,维护一个额外数组作为每个橙子腐烂所需要的时间一开始初始化为无穷大,然后对每一个腐烂橙子进行 bfs
找出和它有接触的所有新鲜橙子更新其腐烂时间,代码如下:
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
int height = grid.size();
int width = grid[0].size();
vector<vector<int>> timing_for_rotting(height, vector<int>(width, INT_MAX));
for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++) {
if (grid[i][j] == 2) {
std::queue<std::pair<int,int>> q;
q.push({i, j});
int timing = 0;
std::unordered_set<int> visited;
while (!q.empty()) {
std::queue<std::pair<int, int>> next_q;
while(!q.empty()) {
std::pair<int, int> current_index = q.front();
q.pop();
int y = current_index.first, x = current_index.second;
if (visited.count(y * width + x) != 0) continue;
else visited.insert(y * width + x);
if (timing_for_rotting[y][x] == INT_MAX ||
timing_for_rotting[y][x] > timing) {
timing_for_rotting[y][x] = timing;
if (hasFreshOrange(y + 1, x, height, width, grid)) next_q.push({y + 1, x});
if (hasFreshOrange(y - 1, x, height, width, grid)) next_q.push({y - 1, x});
if (hasFreshOrange(y, x + 1, height, width, grid)) next_q.push({y, x + 1});
if (hasFreshOrange(y, x - 1, height, width, grid)) next_q.push({y, x - 1});
}
}
q = next_q;
timing++;
}
}
}
}
int ans = 0;
for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++) {
if (grid[i][j] == 1) {
if (timing_for_rotting[i][j] == INT_MAX) {
return -1;
}
else {
ans = max(timing_for_rotting[i][j], ans);
}
}
}
}
return ans;
}
private:
bool hasFreshOrange(int y, int x, int height, int width, const vector<vector<int>>& grid) {
return (y >= 0 && x >= 0 && y < height && x < width && grid[y][x] == 1);
}
};
- 时间复杂度: O(n^4) 时间复杂度不太确定,但是每次进行
bfs
都有可能会重复遍历之前遍历过的位置,所以复杂度肯定在 O(n^2) 以上 - 空间复杂度: O(n^2)
方法二
第一个方法虽然复杂度高,但是由于数据规模不大所以也能过;通过转换思路,可以实际去模拟腐烂的过程,同样也是 bfs
在每一次循环中遍历上一次腐烂的橙子,并将其周围四个橙子腐烂掉加入队列中,等待下一次遍历;如果有某一次遍历中没有出现新腐烂的橙子,那么只需要判断是否所有橙子都腐烂即可,代码如下::
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
int height = grid.size();
int width = grid[0].size();
std::queue<std::pair<int, int>> current_rotten_oranges;
int count_fresh_oranges = 0;
for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++) {
if (grid[i][j] == 2) {
current_rotten_oranges.push({i, j});
} else if (grid[i][j] == 1) {
count_fresh_oranges++;
}
}
}
int iteration = 0;
while (true) {
std::queue<std::pair<int, int>> newly_rotten_oranges;
while (!current_rotten_oranges.empty()) {
std::pair<int, int> index = current_rotten_oranges.front();
current_rotten_oranges.pop();
int y = index.first, x = index.second;
if (hasFreshOrange(y + 1, x, height, width, grid)) {
grid[y + 1][x] = 2;
newly_rotten_oranges.push({y + 1, x});
count_fresh_oranges--;
}
if (hasFreshOrange(y - 1, x, height, width, grid)) {
grid[y - 1][x] = 2;
newly_rotten_oranges.push({y - 1, x});
count_fresh_oranges--;
}
if (hasFreshOrange(y, x + 1, height, width, grid)) {
grid[y][x + 1] = 2;
newly_rotten_oranges.push({y, x + 1});
count_fresh_oranges--;
}
if (hasFreshOrange(y, x - 1, height, width, grid)) {
grid[y][x - 1] = 2;
newly_rotten_oranges.push({y, x - 1});
count_fresh_oranges--;
}
}
if (newly_rotten_oranges.empty()) break;
iteration++;
current_rotten_oranges = newly_rotten_oranges;
}
return count_fresh_oranges == 0? iteration : -1;
}
private:
bool hasFreshOrange(int y, int x, int height, int width, const vector<vector<int>>& grid) {
return (y >= 0 && x >= 0 && y < height && x < width && grid[y][x] == 1);
}
};
- 时间复杂度: O(n^2)
- 空间复杂度: O(n^2)