[每日一题] 994.腐烂的橘子

博主： Richard
发布时间：2024 年 05 月 13 日
99 次浏览
暂无评论
4079字数
分类： LeetCode

> https://leetcode.cn/problems/rotting-oranges/description/?envType=daily-question&envId=2024-05-06

### 模拟

最容易想到的方法就是对每个腐烂橘子模拟其感染路径，遇到重复感染的就取路径较小的那个。题目中地图最大为 $10 \times 10$ ，所以这个方法也可以卡过去：

````c++
class Solution {
public:
    int orangesRotting(std::vector<std::vector<int>>& grid) {
        const int rows = grid.size(), cols = grid[0].size();
        std::vector<std::vector<int>> rot(rows, std::vector<int>(cols, -1));

std::function<void(const int &, const int &)> infect = [&](const int &row, const int &col) {
            if (rot[row][col] == -1)
                rot[row][col] = 0;

if (row - 1 >= 0 && grid[row - 1][col] == 1 &&
                (rot[row - 1][col] == -1 || rot[row - 1][col] > rot[row][col] + 1)) {
                rot[row - 1][col] = rot[row][col] + 1;
                infect(row - 1, col);
            }

if (row + 1 < rows && grid[row + 1][col] == 1 &&
                (rot[row + 1][col] == -1 || rot[row + 1][col] > rot[row][col] + 1)) {
                rot[row + 1][col] = rot[row][col] + 1;
                infect(row + 1, col);
            }

if (col - 1 >= 0 && grid[row][col - 1] == 1 &&
                (rot[row][col - 1] == -1 || rot[row][col - 1] > rot[row][col] + 1)) {
                rot[row][col - 1] = rot[row][col] + 1;
                infect(row, col - 1);
            }

if (col + 1 < cols && grid[row][col + 1] == 1 &&
                (rot[row][col + 1] == -1 || rot[row][col + 1] > rot[row][col] + 1)) {
                rot[row][col + 1] = rot[row][col] + 1;
                infect(row, col + 1);
            }
        };

for (int row = 0, i; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (grid[row][col] != 2)
                    continue;
                infect(row, col);
            }
        }

int res = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 0)
                    continue;

if (rot[i][j] == -1)
                    return -1;

res = std::max(res, rot[i][j]);
            }
        }

return res;
    }
};
````

- 时间复杂度：$O(k \times mn)$ ，其中 $k$ 是初始感染节点数，$m, n$ 分别是 `grid` 数组的行数和列数。
- 空间复杂度：$O(mn)$ 。

### 多源广度优先搜索

如果只有一个腐烂的橘子，那么直接从这个腐烂的橘子开始广搜即可。但题目中可能有多个初始腐烂的橘子，这其实可以看作有一个有一个 "超级节点" 感染了所有这些初始节点，那么对这个 "超级节点" 进行广搜就可以了。

关于判断所有橘子是否都腐烂了，可以用一个变量记录新鲜橘子数，每感染一个新鲜橘子就将该变量减一。最后如果该变量为 0 ，说明所有橘子都被感染了，返回最大时间即可；反之则表示有橘子感染不到，返回 -1 。

```c++
class Solution {
public:
    int orangesRotting(std::vector<std::vector<int>> &grid) {
        const int rows = grid.size(), cols = grid[0].size();
        std::vector<std::pair<int, int>> maneuver({{1, 0}, {-1, 0}, {0, 1}, {0, -1}});

int fresh = 0;
        std::queue<std::pair<int, int>> queue;
        std::vector<std::vector<int>> distance(rows, std::vector<int>(cols, -1));
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 2) {
                    queue.emplace(i, j);
                    distance[i][j] = 0;
                } else if (grid[i][j] == 1) {
                    fresh += 1;
                }
            }
        }

int res = 0, row, col;
        std::pair<int, int> pos;
        while (!queue.empty()) {
            pos = queue.front();
            queue.pop();

for (auto &move : maneuver) {
                row = pos.first + move.first, col = pos.second + move.second;
                if (row < 0 || row >= rows || col < 0 || col >= cols || !grid[row][col] || ~distance[row][col])
                    continue;

distance[row][col] = distance[pos.first][pos.second] + 1;
                queue.emplace(row, col);

if (grid[row][col] == 1) {
                    res = distance[row][col];
                    --fresh;

if (fresh == 0)
                        break;
                }
            }
        }

return fresh ? -1 : res;
    }
};
```

- 时间复杂度：$O(mn)$ ，其中 $m, n$ 分别是 `grid` 数组的行数和列数。
- 空间复杂度：$O(mn)$ 。

最后修改：2024 年 05 月 13 日