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

class Solution
{
public:
    int orangesRotting(vector<vector<int>>& grid)
    {
        using PII = std::pair<int, int>;
        std::queue<PII> q;
        int n = grid.size(), m = grid[0].size();

        // 将所有初始腐烂橘子的坐标加入队列
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                if (grid[i][j] == 2)
                    q.push({i, j});

        int res = 0;
        if (!q.empty()) --res; // 队列非空，初始化分钟数为 -1
        int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};

        // BFS 扩散腐烂
        while (!q.empty()) {
            ++res; // 每遍历一层队列，时间加 1
            int len = q.size();
            while (len--) {
                PII tmp = q.front();
                q.pop();
                int x = tmp.first, y = tmp.second;

                // 遍历四个方向
                for (int i = 0; i < 4; ++i) {
                    int a = x + dx[i], b = y + dy[i];
                    if (a < 0 || a >= n || b < 0 || b >= m || grid[a][b] != 1)
                        continue;
                    q.push({a, b});     // 加入新腐烂的橘子
                    grid[a][b] = 2;     // 标记为腐烂
                }
            }
        }

        // 检查是否有剩余新鲜橘子
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                if (grid[i][j] == 1)
                    return -1; // 仍有新鲜橘子，返回 -1

        return res; // 返回所需的分钟数
    }
};