Build Post Office 系列 | Hyoung's Blog

Build Post Office 系列 | Hyoung's Blog

题设很简单

给定一个二维网格，每个格子要么是房子 1，要么是空地 0，我们需要找到一个空地盖邮局使得所有房子到邮局的距离总和最小。同时，房子和空地都可以随意通过。

在该题设中，因为房子并不会充当一个阻碍物，所以并不需要用 BFS 等算法来计算最短路径，简单地计算两个格子之间在网格上的曼哈顿距离（Manhattan distance）就好了，即

$$d(P,Q) = |P.x - Q.x| + |P.y - Q.y|$$

最先想到的就是暴力算法：穷举网格上的每一个空地，并计算所有房子到它的距离，最后取最小的一个即可。实现起来就是几个嵌套循环，就此略过。最糟糕的情况下时间复杂度为$O(m^2n^2)$。

如果我们进一步观察，可以发现，若我们在同一行上移动，所有房子（$H$）到该行（$r$）的垂直距离（Y 轴方向）不变，其和也因此不变，即 $\sum abs(H^{(i)}.y - r)$ 不变。同理，对于每一列也是如此。在同一列上移动，所有房子到该列的水平距离之和也不变。

充分利用上面的观察，我们就可以提出一个更好的算法，即先算出所有房子到每一行的距离之和以及每一列的距离之和，最后在网格上就可以很快的算出所有房子到某点的距离之和了。

想要算出所有房子到每一行或每一列的距离之和，我们可以进一步抽象，把问题转换成一维上的问题。以到每一行的距离之和为例。首先很直观就可以发现，对于任意两行上的点而言，其垂直距离都是固定不变的。于是我们可以进行水平方向的压缩（不需要水平坐标的信息了），即统计出每一行上的房子数目。而后，问题就变成了，在这个一维的线上算出所有点到任意一点的距离之和。利用前缀和（prefix sum），我们可以在$O(n)$的时间里解决。具体思路就是先从左边扫一遍，记录 $[0,i)$ 范围内的点到 $i$ 的距离之和，又是一个简单的动态规划了，其状态转移方程为

1	prefixCost[i] = prefixCost[i - 1] + prefixSum[i - 1]

其中，prefixSum[i]记录范围 $[0,i]$ 之间点的个数。

类似的，再从右边扫一遍，记录 $(i,n-1]$ 范围内的点到 $i$ 的距离之和。最后把左右结果相加即可。

整体而言，该算法的时间复杂度为$O(mn)$。具体代码实现如下

Read full article from Build Post Office 系列 | Hyoung's Blog