Walls and Gates - Điền khoảng cách đến cổng gần nhất

Cho lưới 2D: -1 (tường), 0 (cổng), INF=2147483647 (phòng trống). Điền mỗi phòng trống bằng khoảng cách đến cổng gần nhất. Không thể đến cổng thì giữ INF.

Ví dụ: lưới 4x4 → kết quả như bảng.

Giải thuật (Multi-source BFS)

Đưa tất cả cổng vào hàng đợi ban đầu. BFS theo tầng (level), mỗi tầng tăng khoảng cách 1. Chỉ cập nhật ô nếu khoảng cách mới nhỏ hơn giá trị hiện tại. Độ phức tạp O(m*n).

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<vector<int>> v) {
    cout << "[";
    for (auto& row : v) {
        cout << "[";
        for (int val : row) cout << val << ", ";
        cout << "],";
    }
    cout << "]" << endl;
}

int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};

class Solution {
public:
    void wallsAndGates(vector<vector<int>>& rooms) {
        int n = rooms.size();
        int m = n ? rooms[0].size() : 0;
        queue<pair<int,int>> q;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (rooms[i][j] == 0)
                    q.push({i, j});

        for (int lvl = 1; !q.empty(); lvl++) {
            int sz = q.size();
            while (sz--) {
                auto [x, y] = q.front(); q.pop();
                for (int i = 0; i < 4; i++) {
                    int nx = x + dir[i][0], ny = y + dir[i][1];
                    if (nx < 0 || ny < 0 || nx >= n || ny >= m || rooms[nx][ny] < lvl)
                        continue;
                    rooms[nx][ny] = lvl;
                    q.push({nx, ny});
                }
            }
        }
    }
};

int main() {
    vector<vector<int>> v = {{2147483647,-1,0,2147483647},
                               {2147483647,2147483647,2147483647,-1},
                               {2147483647,-1,2147483647,-1},
                               {0,-1,2147483647,2147483647}};
    Solution ob;
    ob.wallsAndGates(v);
    print_vector(v);
    return 0;
}

Đầu vào

{{2147483647,-1,0,2147483647},{2147483647,2147483647,2147483647,-1},{2147483647,-1,2147483647,-1},{0,-1,2147483647,2147483647}}

Đầu ra

[[3, -1, 0, 1, ],[2, 2, 1, -1, ],[1, -1, 2, -1, ],[0, -1, 3, 4, ],]