> For the complete documentation index, see [llms.txt](https://nataliekung.gitbook.io/ladder_code/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nataliekung.gitbook.io/ladder_code/qiang-hua-8-matrix/build-post-office.md).

# 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

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

分析

```
先考虑对于一维数组，计算数x到各个数值的距离
for example: A = [1， 2, 5, 4，6]
x = 3时： dis(A, 3) = ｜1 － 3｜＋ |2 - 3| + |4 - 3| + |5 - 3| + |6 - 3|
优化方法是：
1. 先排序A
2. 二分搜索找到3 应该插入的位置： A： ［1， 2， 4 ， 5， 6］，二分搜索得知3应该插入到index = 2 的位置
3. 对于A中位于index = 2之前的数，它们到3的距离是：
  smallPartDis = （3 －1） ＋ （3 － 2） ＝ 3 ＊ 2 － （1 ＋ 2）= 3 * id - (1 +  2)

对于A中位于index = 2之后的数，它们到3的距离是：
 largePartDis = （4 －3） ＋ （5 － 3） ＋ （6 － 3）＝ （4 ＋ 5 ＋ 6） － 3 ＊ 3  
  = (4 ＋ 5 ＋ 6) - 3 * (A.size() - id)

4. 为方便计算，我们算出A的prefix sum, 初始化preSum size 为A.size() + 1, preSum[0] = 0
这样： 
smallPartDis ＝ 3 ＊ 2 － preSum[2]
largePartDis = preSum.back() - preSum[id] - 3 *  (A.size() - id)

对于二维数组, (x, y) 到各个post office的距离是：
dis = |x1 - x| + |y1 - y| + |x2 - x| + |y2 - y| + |x3 - x| + |y3 - y|
可以转化为两个对于x 和y的一维数组：
dis = （|x1 - x| + + |x2 - x| ＋ |x3 - x|） +  （|y1 - y|  ＋ |y2 - y| +  |y3 - y|）
```

答案

```
public class Solution {
    public int shortestDistance(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0] ==null || matrix[0].length == 0 ) {
            return -1;
        }

        int n = matrix.length, m = matrix[0].length;
        int row[] = new int[m + 1];
        int col[] = new int[n + 1];
        int[] sumX = new int[m + 1];
        int[] sumY = new int[n + 1];
        int[][] empty = new int[n * m][2];
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == 1) {
                    row[j] = j;
                    col[i] = i;
                } else {
                    empty[i * m + j][0] = i;
                    empty[i * m + j][1] = j;
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            sumY[i] = sumY[i - 1] + col[i - 1];
        }
        for (int j = 1; j <= m; j++) {
            sumX[j] = sumX[j - 1] + row[j - 1];
        }

        for (int[] pos : empty) {
            int x = getDistance(pos[0], col, sumY);
            int y = getDistance(pos[1], row, sumX);
            min = Math.min(min, x + y);
        }

        return min == Integer.MAX_VALUE ? -1 : min;
    }

    private int getDistance(int x, int[] positions, int[] sum){
        int pos = find(x, positions);
        int dis = pos * x - sum[pos];
        dis += sum[sum.length - 1] - sum[pos] - x * (sum.length - 1 - pos);
        return dis;
    }

    private int find(int x, int[] pos){
        int s = 0, e = pos.length - 1, m;
        while(s + 1 < e){
            m = s + (e - s)/2;
            if(pos[m] < x){
                s = m;
            }else if(pos[m] >= x){
                e = m;
            }
        }
        if(pos[s] == x)
            return s;
        if(pos[e] == x)
            return e;

        return -1;
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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://nataliekung.gitbook.io/ladder_code/qiang-hua-8-matrix/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.