994.md

994. 腐烂的橘子

BFS

class Solution {
private:
    int dir[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int ans = -1, fresh = 0;
        queue<pair<int,int>> q;
        int m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m;i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) {
                    q.push(pair<int,int>{i, j});
                } else if (grid[i][j] == 1) {
                    fresh++;
                }
            }
        }
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                pair<int, int> p = q.front();
                q.pop();
                for (int j = 0; j < 4; j++) {
                    int r = p.first + dir[j][0], c = p.second + dir[j][1];
                    if (r >= 0 && r < m && c >= 0 && c < n && grid[r][c] == 1) {
                        grid[r][c] = 2;
                        q.push(pair<int,int>{r, c});
                        fresh--;
                    }
                }
            }
            ans++;
        }
        if (fresh > 0) {
            return -1;
        }
        return max(ans, 0);
    }
};