1
题目描述
给你一个二维网格,每个格子是房子 1 或者空地 0。找到一个空地修建一个办公室,使得这个办公室到所有的房子的距离之和最小。 返回最小的距离和。如果无法修建,那么返回 -1. 
样例:
返回6。
2
算法分析
1. 因为这个题目要求无解的时候返回 -1 ,那么我们就先想一下无解的情况。

(1)网格不存在,即行数为0或者列数为0;

(2)网格存在,但是没有地方修,也就是没有空地。

之后就要开始要想如何解决这个问题了。

2. 题目是要求所有的房子到某一空地的最小曼哈顿距离和,那我们就有一个朴素的想法,直接枚举所有的空地,求出所有的房子到该空地的曼哈顿距离和,从这些距离和中选取最小的一个即可。
(ps:曼哈顿距离:dis=|x2-x1|+|y2-y1|)
伪代码:
接下来就是改进这个朴素的做法。


3. 观察上述伪代码,显然求所有的房子到某一点的曼哈顿距离和是可以通过预处理实现O(1)询问的。
这里就要先提到有关曼哈顿距离的一个常用技巧了:将曼哈顿距离拆分成 X 轴距离与 Y 轴距离。
设两个点:(x1,y1)、(x2,y2)

曼哈顿距离:dis=|x2-x1|+|y2-y1|


根据上面这个式子,我们就可以把求两个点的曼哈顿距离拆分成求两个点在 X 轴上的距离与求两个点在 Y 轴上的距离。


有了这个拆分,就有了预处理的基础。 


4. 我们现在以对 X 轴距离做预处理为例进行讲解。
我们先预处理出一个rowSum数组,rowSum[i]记录第 i 行一共有几个房子。
那么对于一个点(i,j),从第 0 。。。i 行的所有房子到该点的 X 轴距离和即等同于从第0。。。i 行的所有房子到第 i 行的 X 轴距离和。
用prefixSum1[i]表示从第0。。。i 行的所有房子到第 i 行的一共有多少房子;

用prefixSum2[i]表示从第0。。。i 行的所有房子到第 i 行的X 轴距离和,即得到下式:
根据推导的式子,prefixsum1与prefixsum2都可以通过O(row)的预处理得到。
这样我们就得到了从第0。。。i 行的所有房子到第 i 行的 X 轴距离和。
同理,还可以通过 O(row) 的预处理得到从第 i 。。。n - 1 行的所有房子到第 i 行的 X 轴距离和。


将以上的两个预处理的值相加,即可得到:所有的房子到第 i 行的距离和,将其记为ansRow[i]。


综上,我们就可以通过O(row)的预处理得到所有房子到某一 行的距离和,并记录在ansRow[] 数组里。


5. 通过与第四点相同的思路,我们可以通过一个O(column)的预处理得到所有房子到某一列的距离和,并记录在ansColumn[] 数组里。
于是,所有房子到某一点(i,j)的曼哈顿距离和即为:ansRow[i] + ansColumn[j]。

代码的总体复杂度就下降到了O(row*column)。
3
参考代码
4
面试官角度分析
如果这道题能够用bfs方法写出来可以达到hire的程度。如果能够优化,想到预处理的方法那么就可以拿到strong hire.

5
LintCode 相关问题
http://www.lintcode.com/zh-cn/problem/build-post-office-ii/
《九章算法班》
《系统设计班》
《Big Data 项目实战班》
《Android 项目实战班》
《算法强化班》
正在报名中!
报名登陆官网www.jiuzhang.com
或点击文末“阅读原文”
继续阅读
阅读原文