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

1. 可以通过搜索每一个空位到所有房子的距离或者每一个房子到所有空位的距离（BFS)来找到最小的距离，时间复杂度是O(n*m ^ 2) n 为所有空地，m为所有房子
2. 其实这是Post Office Problem 的follow up问题，在Post Office 问题中，当只有一个邮局和n所房子时，最短距离和一定是最远两个房子的中点，这也帮我们在分段时把时间复杂度减少至n^2。利用这个性质，本题仅涉及一个邮局到所有房子的最短距离和，区别是变成了一个平面（二维）。我们可以通过找到横坐标和纵坐标的中位数来找到所有房子的重心，那么从这个重心向四周延伸，第一个可以到所有房子的点即为答案，因为内圈的一定比外圈的小

class Point {
    int x, y;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
public class Solution {
    /*
     * @param grid: a 2D grid
     * @return: An integer
     */
    private int[] dx = {1,-1,0,0,1,-1,0,0};
    private int[] dy = {1,-1,1,-1,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 0;
        }

        List<Point> houses = new ArrayList<Point>();
        List<Integer> xIndex = new ArrayList<Integer>();
        List<Integer> yIndex = new ArrayList<Integer>();

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    houses.add(new Point(i,j));
                    xIndex.add(i);
                    yIndex.add(j);
                }
            }
        }

        Collections.sort(xIndex);
        Collections.sort(yIndex);
        int xMid = getMedian(xIndex);
        int yMid = getMedian(yIndex);
        //System.out.println(xMid);
        //System.out.println(yMid);
        Point mid = new Point(xMid, yMid);
        Queue<Point> queue = new LinkedList<Point>();
        int[][] isVisited = new int[grid.length][grid[0].length];
        isVisited[xMid][yMid] = 1;
        queue.offer(mid);
        int min = Integer.MAX_VALUE;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Point cur = queue.poll();
                if (grid[cur.x][cur.y] == 0) {
                    int curDistance = 0;
                    for (Point curHouse : houses) {
                        curDistance += getDistance(curHouse, cur);
                    }
                    min = Math.min(min, curDistance);
                }

                for (int j = 0; j < dx.length; j++) {
                    int newX = cur.x + dx[j];
                    int newY = cur.y + dy[j];
                    if (newX >= 0 && newX < grid.length && newY >= 0 && newY < grid[0].length && isVisited[newX][newY] == 0 && grid[newX][newY] == 0) {
                        isVisited[newX][newY] = 1;
                        queue.offer(new Point(newX, newY));
                    }
                }
            }

            if (min != Integer.MAX_VALUE) {
                return min;
            }
        }
        return -1;
    }

    private int getDistance(Point curHouse, Point mid) {
        int dis = Math.abs(curHouse.x - mid.x) + Math.abs(curHouse.y - mid.y);
        //System.out.println(curHouse.x+":"+curHouse.y+":"+dis);
        return dis;

    }

    private int getMedian(List<Integer> list) {
        int k = list.size() / 2;
        if (list.size() % 2 == 0) {
            k--;
        }
        return list.get(k);
    }

}