腐烂的橘子 | 秋招知识库

看示例 1：

统计所有初始就腐烂的橘子的位置，加到列表 $q$ 中，现在 $q = [(0, 0)]$ 。
初始化答案 $ans = 0$ 。模拟橘子腐烂的过程，不断循环，直到没有新鲜橘子，或者 $q$ 为空。
答案加一，在第 $ans = 1$ 分钟，遍历 $q$ 中橘子的四方向相邻的新鲜橘子，把这些橘子腐烂， $q$ 更新为这些橘子的位置，现在 $q = [(0, 1), (1, 0)]$ 。
答案加一，在第 $ans = 2$ 分钟，遍历 $q$ 中橘子的四方向相邻的新鲜橘子，把这些橘子腐烂， $q$ 更新为这些橘子的位置，现在 $q = [(0, 2), (1, 1)]$ 。
答案加一，在第 $ans = 3$ 分钟，遍历 $q$ 中橘子的四方向相邻的新鲜橘子，把这些橘子腐烂， $q$ 更新为这些橘子的位置，现在 $q = [(2, 1)]$ 。
答案加一，在第 $ans = 4$ 分钟，遍历 $q$ 中橘子的四方向相邻的新鲜橘子，把这些橘子腐烂， $q$ 更新为这些橘子的位置，现在 $q = [(2, 2)]$ 。
由于没有新鲜橘子，退出循环。

为了判断是否有永远不会腐烂的橘子（如示例 2），我们可以统计初始新鲜橘子的个数 $fresh$ 。在 BFS 中，每有一个新鲜橘子被腐烂，就把 $fresh$ 减一，这样最后如果发现 $fresh > 0$ ，就意味着有橘子永远不会腐烂，返回 $- 1$ 。

代码实现时，在 BFS 中要将 $grid [i] [j] = 1$ 的橘子修改成 $2$ （或者其它不等于 $1$ 的数），这可以保证每个橘子加入 $q$ 中至多一次。如果不修改，我们就无法知道哪些橘子被腐烂过了，比如示例 1 中 $(0, 1)$ 去腐烂 $(1, 1)$ ，而 $(1, 1)$ 在此之后又重新腐烂 $(0, 1)$ ，如此反复，程序就会陷入死循环。读者可以注释掉下面代码中的 grid[i][j] = 2 这行代码试试。

关于 BFS 的原理，请看【基础算法精讲 13】。

答疑

问：如果代码不在 while 中判断 $fresh > 0$ ，会发生什么？

答：会在腐烂完所有新鲜橘子后，多循环一次。这会导致 $ans$ 比实际多 $1$ 。

Python 解法1C++ 解法1

python

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        fresh = 0
        q = []
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                if x == 1:
                    fresh += 1  # 统计新鲜橘子个数
                elif x == 2:
                    q.append((i, j))  # 一开始就腐烂的橘子

        ans = 0
        while q and fresh:
            ans += 1  # 经过一分钟
            tmp = q
            q = []
            for x, y in tmp:  # 已经腐烂的橘子
                for i, j in (x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1):  # 四方向
                    if 0 <= i < m and 0 <= j < n and grid[i][j] == 1:  # 新鲜橘子
                        fresh -= 1
                        grid[i][j] = 2  # 变成腐烂橘子
                        q.append((i, j))

        return -1 if fresh else ans

cpp

// C++ 版待补充

C++ 解法2

cpp

class Solution {
    int DIRECTIONS[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 四方向

public:
    int orangesRotting(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int fresh = 0;
        vector<pair<int, int>> q;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    fresh++; // 统计新鲜橘子个数
                } else if (grid[i][j] == 2) {
                    q.emplace_back(i, j); // 一开始就腐烂的橘子
                }
            }
        }

        int ans = 0;
        while (fresh && !q.empty()) {
            ans++; // 经过一分钟
            auto tmp = move(q); // move 后 q 为空
            for (auto& [x, y] : tmp) { // 已经腐烂的橘子
                for (auto& d : DIRECTIONS) { // 四方向
                    int i = x + d[0], j = y + d[1];
                    if (0 <= i && i < m && 0 <= j && j < n && grid[i][j] == 1) { // 新鲜橘子
                        fresh--;
                        grid[i][j] = 2; // 变成腐烂橘子
                        q.emplace_back(i, j);
                    }
                }
            }
        }

        return fresh ? -1 : ans;
    }
};

复杂度分析

时间复杂度： $O (m n)$ ，其中 $m$ 和 $n$ 分别为 $grid$ 的行数和列数。
空间复杂度： $O (m n)$ 。

变形题（2025.7.16 添加）

你可以把至多 $1$ 个 $1$ 改成 $2$ ，最小化最终新鲜橘子个数。
你可以把至多 $k$ 个 $1$ 改成 $2$ ，最小化最终新鲜橘子个数。
你可以把至多 $1$ 个 $2$ 改成 $1$ ，最大化最终新鲜橘子个数。
你可以把至多 $k$ 个 $2$ 改成 $1$ ，最大化最终新鲜橘子个数。

欢迎在评论区分享你的思路/代码。

更多相似题目，见下面网格图题单中的 BFS。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

答疑 ​

复杂度分析 ​

变形题（2025.7.16 添加） ​

分类题单 ​

答疑

复杂度分析

变形题（2025.7.16 添加）

分类题单