Build Post Office

Given a 2D grid, each cell is either an house 1 or empty 0 (the number zero, one), find the place to build a post office, the distance that post office to all the house sum is smallest. Return the smallest distance. Return -1 if it is not possible.

Notice

• You can pass through house and empty.
• You only build post office on an empty.

Example

Given a grid:

0 1 0 0
1 0 1 1
0 1 0 0

return6. (Placing a post office at (1,1), the distance that post office to all the house sum is smallest.)

S1: 存下所有有房子的点，再遍历空点求最小距离 O(mnk) k为房子数

    int shortestDistance(vector<vector<int>>& grid) {
        int m = grid.size();
        if (m == 0) {
            return -1;
        }
        int n = grid[0].size();
        list<int> houseX;
        list<int> houseY;
        int result = INT_MAX;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    houseX.push_back(i);
                    houseY.push_back(j);
                }
            }
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0) {
                    int dist = 0;
                    for (int k : houseX) {
                        dist += abs(k - i);
                    }
                    for (int k : houseY) {
                        dist += abs(k - j);
                    }
                    if (dist < result) {
                        result = dist;
                    }
                }
            }
        }
        if (result == INT_MAX) {
            return -1;
        } else {
            return result;
        }

    }

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.

For example, given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2):

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

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.

S: 逆向思维BFS O(mnk) k是房子数目

以每个房子为起始进行BFS记录房子到每个空地的距离，累加。

用count数组记录每块空地被bfs访问的次数，若count小于房子数目则有房子不可到达，排除。

class Solution {
public:
    int shortestDistance(vector<vector<int>>& grid) {
        int m = grid.size();
        if (m == 0) {
            return -1;
        }
        int n = grid[0].size();
        int houseCount = 0;
        vector<vector<int>> dist(m, vector<int>(n, 0));
        vector<vector<int>> count(m, vector<int>(n, 0));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    houseCount++;
                    bfs(grid, i, j, dist, count);
                }
            }
        }
        int result = INT_MAX;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0 && houseCount == count[i][j]) {
                    result = min(result, dist[i][j]);
                }
            }
        }
        return result == INT_MAX? -1: result;
    }
private:
    void bfs(vector<vector<int>>& grid, int x, int y, vector<vector<int>>& dist,
             vector<vector<int>>& count) {
        queue<Node> q;
        int curDist = 0;
        vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false));
        q.push(Node(x, y, curDist));
        while (!q.empty()) {
            Node node = q.front();
            q.pop();
            dist[node.x][node.y] += node.dist;
            count[node.x][node.y]++;
            vector<int> dx{1, 0, -1, 0};
            vector<int> dy{0, 1, 0, -1};
            for (int i = 0; i < 4; ++i) {
                int x1 = node.x + dx[i];
                int y1 = node.y + dy[i];
                if (x1 < grid.size() && x1 >= 0 && y1 < grid[0].size() && y1 >= 0 && grid[x1][y1] == 0 && !visited[x1][y1] && grid[x1][y1] != -1) {
                    visited[x1][y1] = true;
                    q.push(Node(x1, y1, node.dist + 1));
                }
            }
        }
    }
    struct Node {
        int x;
        int y;
        int dist;
        Node(int a, int b, int d): x(a), y(b), dist(d) {}
    };
};