题目地址：

https://www.lintcode.com/problem/build-post-office/description

给定一个二维$0-1$矩阵，$0$代表空地，$1$代表房子。允许在空地上建一个邮局，要求这个邮局距离所有房子的曼哈顿距离之和达到最小，问这个最小距离是多少。

直接用暴力法即可。先算一下每一行和每一列有多少个房子，然后将曼哈顿距离分成两个方向分别统计距离和。直接枚举每个空地，算一下曼哈顿距离和即可。代码如下：

public class Solution { /** * @param grid: a 2D grid * @return: An integer */ public int shortestDistance(int[][] grid) { // write your code here int m = grid.length, n = grid[0].length; // 算一下每行有多少个房子，每列有多少个房子 int[] cntRow = new int[m], cntCol = new int[n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 1) { cntRow[i]++; cntCol[j]++; } } } int res = Integer.MAX_VALUE; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { // 枚举空地 if (grid[i][j] == 0) { int dis = 0; // 累加x轴方向的距离和 for (int k = 0; k < m; k++) { dis += cntRow[k] * Math.abs(k - i); // 发现累加的距离已经大于等于了之前算出来过的最短距离和了，直接退出 if (dis >= res) { break; } } // 累加y轴方向的距离和 for (int k = 0; k < n; k++) { dis += cntCol[k] * Math.abs(k - j); if (dis >= res) { break; } } // 更新答案 res = Math.min(res, dis); } } } return res; } }

时间复杂度$O(k(m+n))$，$k$是空地数量；空间复杂度$O(m+n)$。