286. Walls and Gates

bfs O(mn) time O(mn) space

class Solution {
public:
    void wallsAndGates(vector<vector<int>>& rooms) {
        if (rooms.empty() || rooms[0].empty()) return;
        int m = rooms.size(), n = rooms[0].size();
        queue<pair<int, int>> q;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (rooms[i][j] == 0) {
                    q.emplace(i, j);
                }
            }
        }
        int dr[] = {0, 0, 1, -1}, dc[] = {1, -1, 0, 0};
        while (!q.empty()) {
            auto [r, c] = q.front(); q.pop();
            for (int j = 0; j < 4; ++j) {
                int rr = r + dr[j], cc = c + dc[j];
                if (rr < 0 || rr >= m || cc < 0 || cc >= n || rooms[rr][cc] != INT_MAX) continue;
                q.emplace(rr, cc);
                rooms[rr][cc] = rooms[r][c] + 1; // 提前修改可以避免后期处理的麻烦
            }
        }
    }
};

class Solution {
public:
    void wallsAndGates(vector<vector<int>>& rooms) {
        if (rooms.empty() || rooms[0].empty()) return;
        int m = rooms.size(), n = rooms[0].size();
        queue<pair<int, int>> q;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (rooms[i][j] == 0) {
                    q.emplace(i, j);
                }
            }
        }
        int dr[] = {0, 0, 1, -1}, dc[] = {1, -1, 0, 0};
        int dist = 1;
        while (!q.empty()) {
            for (int i = q.size(); i > 0; --i) {
                auto [r, c] = q.front(); q.pop();
                for (int j = 0; j < 4; ++j) {
                    int rr = r + dr[j], cc = c + dc[j];
                    if (rr < 0 || rr >= m || cc < 0 || cc >= n || rooms[rr][cc] != INT_MAX) continue;
                    q.emplace(rr, cc);
                    rooms[rr][cc] = dist; // 一定要提前修改
                }
            }
            ++dist;
        }
    }
};