[LeetCode] 317. Shortest Distance from All Buildings

 

Problem: 317. Shortest Distance from All Buildings
Category: Graph Theory
Algorithm: BFS
Company: DoorDash, Google, Facebook, Microsoft, Oracle etc.

class Solution {
private:
    int bfs(vector<vector<int>> &grid, int sx, int sy, int houses) {
        const int dr[] = {+0, +1, +0, -1};
        const int dc[] = {+1, +0, -1, +0};
        int n = grid.size();
        int m = grid[0].size();
        vector<vector<int>> dist(n, vector<int>(m, 0));
        vector<vector<bool>> vis(n, vector<bool>(m, false));
        queue<pair<int, int>> pq;
        pq.push(make_pair(sx, sy));
        vis[sx][sy] = true;
        int sum = 0;
        while (pq.size() and houses > 0) {
            pair<int, int> cur = pq.front(); pq.pop();
            for (int d = 0; d < 4; d++) {
                int x = cur.first + dr[d];
                int y = cur.second + dc[d];
                if (x >= 0 and x < n and y >= 0 and y < m and grid[x][y] != 2 and vis[x][y] == false) {
                    dist[x][y] = dist[cur.first][cur.second] + 1;
                    vis[x][y] = true;
                    if (grid[x][y] == 0) {
                        pq.push(make_pair(x, y));
                    } else {
                        sum += dist[x][y];
                        --houses;
                    }
                }
            }
        }
        if (houses > 0) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (grid[i][j] == 0 and vis[i][j]) {
                        grid[i][j] = 2;
                    }
                }
            }
            return INT_MAX;
        }
        return sum;
    }
 
public:
    int shortestDistance(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        int houses = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    ++houses;
                }
            }
        }
        int mini = INT_MAX;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 0) {
                    int cost = bfs(grid, i, j, houses);
                    mini = min(mini, cost);
                }
            }
        }
        return mini == INT_MAX ? -1 : mini;
    }
};