574.Build Post Office

1.Description(Hard)

Given a 2D grid, each cell is either an house1or empty0(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-1if 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.)

2.Code

1.首先找到所有房子的重心。找所有房子x值的median和y值的median（如果是奇数个就是排序后取中间值，如果是偶数则取中间两个数再取平均值）即为重心。

2.然后用bfs来搜索。将重心加入queue中，然后开始一圈一圈（将出队的每个点周围八个点加入队中）向外找，用的是和逐层遍历二叉树的类似的方法（即在每一层开始的时候记录一下本层的点的个数，然后一次出队这么多点即可将本层的点全部出队）。每一圈结束时，返回该圈上的点作为post office能取的最小值，如果存在则停止搜索。即如果存在可以作为post office的点，则外圈点到各个房子的距离一定不会比内圈点更优。

https://zhengyang2015.gitbooks.io/lintcode/build_post_office_573.html

public int m,n;
    public int[] deltaX={0,0,1,-1,1,1,-1,-1};
    public int[] deltaY={1,-1,0,0,1,-1,1,-1};
    public int shortestDistance(int[][] grid) {
        if(grid==null || grid.length==0 || grid[0].length==0){
            return -1;
        }
        m=grid.length;
        n=grid[0].length;

        //确定房子的位置，并把房子的位置记录下来
        ArrayList<Point> house=new ArrayList<Point>();
        ArrayList<Integer> xArr=new ArrayList<Integer>();
        ArrayList<Integer> yArr=new ArrayList<Integer>();
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==1){
                    house.add(new Point(i,j));
                    xArr.add(i);
                    yArr.add(j);
                }
            }
        }

        //no empty space
        if(house.size()==m*n){
            return -1;
        }
        if(house.size()==0){
            return 0;
        }

        int medX=getMedian(xArr);
        int medY=getMedian(yArr);

        boolean[][] visited=new boolean[m][n];
        visited[medX][medY]=true;

        Point root=new Point(medX,medY);
        Queue<Point> queue=new LinkedList<Point>();
        queue.offer(root);
        int min=Integer.MAX_VALUE;

        while(!queue.isEmpty()){
            int size=queue.size();
            for(int i=0;i<size;i++){
                Point current=queue.poll();
                //如果重心是空地，得到Min，不是的话在他周围一圈找min
                if(grid[current.x][current.y]==0){
                    min=Math.min(min, distance(house,current));
                }
                for(int direction=0;direction<8;direction++){
                    int neighborX=current.x+deltaX[direction];
                    int neighborY=current.y+deltaY[direction];
                    if(neighborX>=0 && neighborX<m && neighborY>=0 && neighborY<n && !visited[neighborX][neighborY]){
                        visited[neighborX][neighborY]=true;
                        queue.offer(new Point(neighborX,neighborY));
                    }
                }               
            }
            //每一圈结束时，返回该圈上的点作为post office能取的最小值，如果存在则停止搜索。
            //即如果存在可以作为post office的点，则外圈点到各个房子的距离一定不会比内圈点更优。
            if(min!=Integer.MAX_VALUE){
                return min;
            }
        }
        return -1;
    }

    public int getMedian(ArrayList<Integer> arr){
        Collections.sort(arr);

        int Median = arr.get(arr.size() / 2);

        if(arr.size() % 2 == 0){
            Median = (Median + arr.get(arr.size() / 2 - 1)) / 2;
        }

        return Median;
    }

    public int distance(ArrayList<Point> house,Point current){
        int sum=0;
        for(Point node:house){
            sum=sum+Math.abs(node.x-current.x)+Math.abs(node.y-current.y);
        }
        return sum;
    }