XTAO's Tech Blog
0%

[Leetcode]994. Rotting Oranges (C++)

发表于 更新于 分类于 评论数：
4.6k 4 分钟

题目描述

题目链接：994. Rotting Oranges

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.

例子

例子 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 only 0, 1, or 2.

解题思路

方法一

通过找最短时间，问题可以转化问对每一个新鲜橙子，找离它最近的发霉橙子；这样就变成了一个搜索问题，而按找最近的思路，很明显应该应该用 bfs，我一开始想了一个不太直观而且比较麻烦的方法，维护一个额外数组作为每个橙子腐烂所需要的时间一开始初始化为无穷大，然后对每一个腐烂橙子进行 bfs 找出和它有接触的所有新鲜橙子更新其腐烂时间，代码如下：

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
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 在每一次循环中遍历上一次腐烂的橙子，并将其周围四个橙子腐烂掉加入队列中，等待下一次遍历；如果有某一次遍历中没有出现新腐烂的橙子，那么只需要判断是否所有橙子都腐烂即可，代码如下：：

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

推荐文章