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.)

因为有了墙，所以重心不再一定是最优距离和。可以搜索（BFS)所有房子到每一个空地的距离，并且对于每一个空地，记录是否所有房子都到达过，并从中选取最小的距离和即可

public class Solution {
    /**
     * @param grid a 2D grid
     * @return an integer
     */
    class Pair {
        int n;
        int m;
        public Pair (int n, int m) {
            this.n = n;
            this.m = m;
        }
    }


    public int HOUSE = 1;
    public int EMPTY = 0;
    public int WALL = 2;

    public int[] deltaN = {1, -1, 0, 0};
    public int[] deltaM = {0, 0, -1, 1};

    public int shortestDistance(int[][] grid) {
        // Write your code here
        if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
            return -1;
        }

        //get the house list
        ArrayList<Pair> houseList = getHouseList(grid);


        //get the smallest count by bfs through all houses to all empty points
        return countMinDistance(grid, houseList);
    }

    public ArrayList<Pair> getHouseList(int[][] grid) {
        ArrayList<Pair> ans = new ArrayList<Pair>();

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == HOUSE) {
                    ans.add(new Pair(i, j));
                }
            }
        }

        return ans;
    }

    public int countMinDistance(int[][] grid, ArrayList<Pair> houseList) {
        int[][] sumDistance = new int[grid.length][grid[0].length];
        int[][] visitCount = new int[grid.length][grid[0].length];

        for (Pair house : houseList) {
            bfsToAllPoint(house, grid, sumDistance, visitCount);
        }

        int minSum = Integer.MAX_VALUE;
        boolean finished = false;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == EMPTY && visitCount[i][j] == houseList.size()) {
                    minSum = Math.min(minSum, sumDistance[i][j]);
                    finished = true;
                }
            }
        }

        if (finished) {
            return minSum;
        }

        return -1;
    }


    public void bfsToAllPoint(Pair house, 
                              int[][] grid,
                              int[][] sumDistance,
                              int[][] visitCount) {

        Queue<Pair> houseQueue = new LinkedList<Pair>();
        boolean[][] isVisited = new boolean[grid.length][grid[0].length];

        houseQueue.offer(house);
        isVisited[house.n][house.m] = true;

        int count = 0;
        while (!houseQueue.isEmpty()) {
            int size = houseQueue.size();
            count++;
            for (int i = 0; i < size; i++) {
                Pair cur = houseQueue.poll();
                for (int j = 0; j < 4; j++) {
                    Pair neighbor = new Pair(
                            cur.n + deltaN[j],
                            cur.m + deltaM[j]
                        );

                    if (!isInbound(neighbor, grid)) {
                        continue;
                    }

                    if (isVisited[neighbor.n][neighbor.m]) {
                        continue;
                    }

                    isVisited[neighbor.n][neighbor.m] = true;
                    sumDistance[neighbor.n][neighbor.m] += count;
                    visitCount[neighbor.n][neighbor.m]++;
                    houseQueue.offer(neighbor);
                }
            }
        }

    }

    public boolean isInbound(Pair pair, int[][] grid) {
        if (pair.n < 0 || pair.n >= grid.length) {
            return false;
        }

        if (pair.m < 0 || pair.m >= grid[0].length) {
            return false;
        }

        return grid[pair.n][pair.m] == EMPTY;
    }
}