Given a 2D grid, each cell is either a wall2, an house1or empty0(the number zero, one, two), find a place to build a post office so that the sum of the distance from the post office to all the houses is smallest.

Return the smallest sum of distance. Return-1if it is not possible.

Notice

• You cannot pass through wall and house, but can pass through empty.
• You only build post office on an empty.

Have you met this question in a real interview?

Yes

Example

Given a grid:

0 1 0 0 0
1 0 0 2 1
0 1 0 0 0

return8, You can build at(1,1). (Placing a post office at (1,1), the distance that post office to all the house sum is smallest.)

Challenge

Solve this problem withinO(n^3)time.

class Solution {
public:

    class Coordinate {
        public:
        int x, y;
        Coordinate(int _x, int _y):x(_x), y(_y){};
    };

    /**
     * @param grid a 2D grid
     * @return an integer
     */

    int shortestDistance(vector<vector<int>>& grid) {
        // Write your code here
        if (grid.empty() || grid[0].empty()) {
            return -1;
        }
        int n = grid.size(), m = grid[0].size();
        vector<vector<int>> distSum(n , vector<int>(m, 0));
        vector<vector<int>> visitedTimes(n, vector<int>(m, 0));

        // bfs from all building get distSum and visitSum
        int house_num = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == 1) {
                    ++house_num;
                    bfs(Coordinate(i, j), distSum, visitedTimes, grid);
                }
            }
        }

        // check all empty space to get minimum distanceSum
        int smallest = INT_MAX;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == 0 && visitedTimes[i][j] == house_num) {
                    smallest = min(distSum[i][j], smallest);
                }
            }
        }

        if (smallest == INT_MAX) {
            return -1;
        }

        return smallest;
    }

    void bfs(Coordinate start, vector<vector<int>> &distSum, vector<vector<int>> &visitedTimes, vector<vector<int>> &grid) {
        int n = distSum.size(), m = distSum[0].size();
        vector<vector<bool>> visited(n, vector<bool>(m, false));

        queue<Coordinate> q;
        q.push(start);
        visited[start.x][start.y] = true;
        vector<vector<int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        int step = 0;
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                Coordinate cur = q.front(); q.pop();
                ++visitedTimes[cur.x][cur.y];
                distSum[cur.x][cur.y] += step;

                for (auto& dir : dirs) {
                    int nx = cur.x + dir[0];
                    int ny = cur.y + dir[1];
                    if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
                            continue;
                    }
                    if (visited[nx][ny] || grid[nx][ny] != 0) {
                        continue;
                    }
                    visited[nx][ny] = true;
                    q.push(Coordinate(nx, ny));
                }
            }
            ++step;
        }
    }
};