317. Shortest Distance from All Buildings

You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2, where:

• Each 0 marks an empty land which you can pass by freely.

• Each 1 marks a building which you cannot pass through.

• Each 2 marks an obstacle which you cannot pass through.

Example:

Input: [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]

1 - 0 - 2 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0

Output: 7 

Explanation: Given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2),
             the point (1,2) is an ideal empty land to build a house, as the total 
             travel distance of 3+3+1=7 is minimal. So return 7.

Note: There will be at least one building. If it is not possible to build such house according to the above rules, return -1.

// BFS
int shortestDistance(vector<vector<int>>& grid) { // time: O(m^2 * n^2); space: O(m * n)
    int res = numeric_limits<int>::max(), search_val = 0, m = grid.size(), n = grid[0].size();
    // vector<vector<int> > sums = grid;
    vector<vector<int> > sums(m, vector<int> (n, 0));
    vector<vector<int> > dirs({{-1, 0}, {1, 0}, {0, -1}, {0, 1}});
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            // Start from each building
            if (grid[i][j] == 1) {
                res = numeric_limits<int>::max();
                // vector<vector<int> > dist = grid; // distance map
                vector<vector<int> > dist(m, vector<int> (n, 0));
                queue<pair<int, int> > q({{i, j}});
                // BFS
                while (!q.empty()) {
                    auto t = q.front(); q.pop();
                    for (const vector<int>& dir : dirs) {
                        int x = t.first + dir[0], y = t.second + dir[1];
                        if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == search_val) {
                            --grid[x][y]; // similar to mark as visited
                            dist[x][y] = dist[t.first][t.second] + 1;
                            // sums[x][y] += dist[x][y] - 1; // building is 1 in the very beginning
                            sums[x][y] += dist[x][y];
                            q.push({x, y});
                            res = min(res, sums[x][y]);
                        }
                    }
                }
                --search_val;
            }
        }
    }
    return res != numeric_limits<int>::max() ? res : -1;
}

// BFS
int shortestDistance(vector<vector<int>>& grid) { // time: O(m^2 * n^2); space: O(m * n)
    int res = numeric_limits<int>::max(), buildingCnt = 0, m = grid.size(), n = grid[0].size();
    // sums: accumulated distance for each grid to reachable buildings
    // cnt: total number of buildings reachable from each grid
    vector<vector<int> > sums(m, vector<int> (n, 0)), cnt = sums;
    vector<vector<int> > dirs({{-1, 0}, {1, 0}, {0, -1}, {0, 1}});
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] == 1) {
                ++buildingCnt;
                queue<pair<int, int> > q({{i, j}});
                vector<vector<bool> > visited(m, vector<bool> (n, false));
                int level = 1;
                while (!q.empty()) {
                    int size = q.size();
                    for (int i = 0; i < size; ++i) {
                        auto t = q.front(); q.pop();
                        for (const vector<int>& dir : dirs) {
                            int x = t.first + dir[0], y = t.second + dir[1];
                            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 0 && !visited[x][y]) {
                                sums[x][y] += level;
                                ++cnt[x][y];
                                visited[x][y] = true;
                                q.push({x, y});
                            }
                        }
                    }
                    ++level;
                }
            }
        }
    }
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] == 0 && cnt[i][j] == buildingCnt) {
                res = min(res, sums[i][j]);
            }
        }
    }
    return res == numeric_limits<int>::max() ? -1 : res;
}