Untitled

class Solution {
public:
    int shortestDistance(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dist(m, vector<int>(n, 0));
        vector<vector<int>> reach(m, vector<int>(n, 0));
        int total_buildings = 0;

        // 找到所有的建築物，並從每個建築物 BFS
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    total_buildings++;
                    bfs(grid, i, j, dist, reach);
                }
            }
        }

        int minDist = INT_MAX;
        // 找到空地，同時被所有建築物 reach 的最小距離
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0 && reach[i][j] == total_buildings) {
                    minDist = min(minDist, dist[i][j]);
                }
            }
        }

        return minDist == INT_MAX ? -1 : minDist;
    }

    void bfs(vector<vector<int>>& grid, int row, int col,
             vector<vector<int>>& dist, vector<vector<int>>& reach) {
        int m = grid.size(), n = grid[0].size();
        queue<pair<int, int>> q;
        q.push({row, col});

        vector<vector<bool>> visited(m, vector<bool>(n, false));
        visited[row][col] = true;

        int level = 1;
        vector<pair<int, int>> dirs = {{0,1}, {1,0}, {-1,0}, {0,-1}};

        while (!q.empty()) {
            int size = q.size();
            while (size--) {
                auto [r, c] = q.front(); q.pop();
                for (auto [dr, dc] : dirs) {
                    int nr = r + dr, nc = c + dc;
                    if (nr >= 0 && nr < m && nc >= 0 && nc < n &&
                        !visited[nr][nc] && grid[nr][nc] == 0) {
                        visited[nr][nc] = true;
                        dist[nr][nc] += level;
                        reach[nr][nc]++;
                        q.push({nr, nc});
                    }
                }
            }
            level++;
        }
    }
};