腐烂橘子图问题

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        std::queue<std::pair<int, int>> qe; // 保存烂橘子得i,j坐标
        int fresh = 0; // 记录新鲜水果数量
        for (int i=0; i<grid.size(); i++) {
            for (int j=0; j<grid[i].size(); j++) {
                if (grid[i][j]==2) qe.push({i,j});
                else if (grid[i][j] == 1) fresh++;
            }
        }
        int count = 0; // 返回次数
        // 烂橘子移动坐标，上下左右
        std::vector<std::pair<int, int>> dirts{{-1,0}, {1,0}, {0,1}, {0,-1}};
        while(!qe.empty()) {
            int size = qe.size(); // 当前队列大小
            bool flag = false;    //  标记每层是否出现橘子腐烂，腐烂了count+1
            while(size>0){
                auto pair = qe.front();
                qe.pop();

                // 对四个方向上得橘子进行判断
                for (auto direct: dirts) {
                    int i = pair.first + direct.first;
                    int j = pair.second + direct.second;
                    // 校验移动得新坐标i，j，并且移动后当前时新鲜橘子更新为烂橘子
                    if (i>=0 && i<grid.size() && j>=0 && j<grid[0].size() && grid[i][j] == 1) {
                        grid[i][j] = 2; // 更新烂橘子
                        qe.push({i,j}); // 将新烂橘子坐标添加到队列中
                        fresh--;        // 新鲜橘子数量-1
                        flag = true;    // 标记有出现向四周腐烂橘子情况
                    }
                }
                size--;
            }
            if (flag) count++; // 只有腐烂了才会次数+1,可能出现孤立腐烂橘子
        }
        return fresh ? -1 : count;
    }
};
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