994. 腐烂的橘子

难度：🟡 Medium | 标签：图论、BFS | 状态：⬜ LeetCode 链接

思路

多源 BFS：所有腐烂橘子先入队，按层扩散。 答案 = 最后一层的层数；扩散完仍有新鲜橘子 → 返回 -1。

代码

class Solution {
public:
    int orangesRotting(vector<vector<int>>& g) {
        int R = g.size(), C = g[0].size(), fresh = 0;
        queue<pair<int,int>> q;
        for (int i = 0; i < R; ++i)
            for (int j = 0; j < C; ++j) {
                if (g[i][j] == 2) q.push({i, j});
                else if (g[i][j] == 1) ++fresh;
            }
        int t = 0, dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
        while (!q.empty() && fresh) {
            int sz = q.size();
            for (int i = 0; i < sz; ++i) {
                auto [r, c] = q.front(); q.pop();
                for (int d = 0; d < 4; ++d) {
                    int nr = r + dr[d], nc = c + dc[d];
                    if (nr < 0 || nc < 0 || nr >= R || nc >= C || g[nr][nc] != 1) continue;
                    g[nr][nc] = 2;
                    --fresh;
                    q.push({nr, nc});
                }
            }
            ++t;
        }
        return fresh ? -1 : t;
    }
};

复杂度

• 时间 O(R · C)，空间 O(R · C)

易错 / 回顾

• 没有新鲜橘子时返回 0，不是 -1
• BFS 推进要按”层”，t 才是最少分钟数
• 不要单源 BFS——会错（多个腐烂橘子可能同时影响）