Khoảng cách ngắn nhất từ tất cả tòa nhà trong C++

Muốn xây nhà trên đất trống sao cho tổng khoảng cách đến tất cả tòa nhà là nhỏ nhất. Chỉ di chuyển 4 hướng (lên, xuống, trái, phải). Lưới 2D: 0 = đất trống, 1 = tòa nhà (không đi qua), 2 = chướng ngại vật.

Ví dụ:

3 tòa nhà tại (0,0), (0,4), (2,2), chướng ngại vật tại (0,2). Điểm lý tưởng (1,2) với tổng khoảng cách 3+3+1=7.

Phương pháp giải

Từ mỗi tòa nhà (1), chạy BFS tính khoảng cách đến mọi ô đất trống (0). Cộng dồn khoảng cách vào mảng dist[][], đếm số tòa nhà có thể đến ô đó trong reach[][]. Cuối cùng, tìm ô đất trống có reach = tổng số tòa nhà và dist nhỏ nhất.

Ví dụ chương trình

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

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

class Solution {
public:
    int shortestDistance(vector>& grid) {
        int ret = INT_MAX;
        int n = grid.size(), m = grid[0].size();
        int numberOfOnes = 0;
        vector> dist(n, vector(m));
        vector> reach(n, vector(m));
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    numberOfOnes++;
                    queue> q;
                    q.push({i, j});
                    set> visited;
                    for (int lvl = 1; !q.empty(); lvl++) {
                        int sz = q.size();
                        while (sz--) {
                            auto curr = q.front(); q.pop();
                            int x = curr.first, y = curr.second;
                            for (int k = 0; k < 4; k++) {
                                int nx = x + dir[k][0], ny = y + dir[k][1];
                                if (nx < 0 || ny < 0 || nx >= n || ny >= m || 
                                    visited.count({nx,ny}) || grid[nx][ny] != 0) continue;
                                visited.insert({nx, ny});
                                dist[nx][ny] += lvl;
                                reach[nx][ny]++;
                                q.push({nx, ny});
                            }
                        }
                    }
                }
            }
        }
        
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (grid[i][j] == 0 && reach[i][j] == numberOfOnes)
                    ret = min(ret, dist[i][j]);
        
        return ret == INT_MAX ? -1 : ret;
    }
};

int main() {
    Solution ob;
    vector> grid = {{1,0,2,0,1}, {0,0,0,0,0}, {0,0,1,0,0}};
    cout << ob.shortestDistance(grid);
    return 0;
}

Đầu vào

[[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]

Đầu ra

7