# 574.Build Post Office

## 1.Description(Hard)

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
```

return`6`. (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;
    }
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://junnie.gitbook.io/nine-chapter/3.breadth-first-search/574.build-post-office.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.