【题目描述】
Given a 2D grid, each cell is either a wall 2, an house 1 or empty 0 (the number zero, one, two), find a place to build a post office so that the sum of the distance from the post office to all the houses is smallest.
Return the smallest sum of distance. Return -1 if it is not possible.
Notice:
1. You cannot pass through wall and house, but can pass through empty.
2. You only build post office on an empty.
Example
Given a grid:
0 1 0 0 0
1 0 0 2 1
0 1 0 0 0
return 8, You can build at (1,1). (Placing a post office at (1,1), the distance that post office to all the house sum is smallest.)
给出一个二维的网格，每一格可以代表墙 2 ，房子 1，以及空 0 (用数字0,1,2来表示)，在网格中找到一个位置去建立邮局，使得所有的房子到邮局的距离和是最小的。
返回所有房子到邮局的最小距离和，如果没有地方建立邮局，则返回-1。
注意：
1. 你不能穿过房子和墙，只能穿过空地。
2. 你只能在空地建立邮局。
样例
给出一个网格：
0 1 0 0 0
1 0 0 2 1
0 1 0 0 0
返回 8，你可以在(1,1)处建立邮局 (在(1,1)处建立邮局，所有房子到邮局的距离是最近的)。
【题目链接】
www.lintcode.com/en/problem/build-post-office-ii/
【题目解析】
1. 将数组扫描一遍找到所有房子。
2. 为每一个房子建立一个距离矩阵，计算该房子到所有0点的距离。即distance[i][j][k]为k房子到grid[i][j]上的点的距离。计算距离的时候用bfs搜索。
3. 然后遍历图上所有为0的点，查询k张距离矩阵，将所有房子到该点的距离加起来即为在该点建邮局的距离总和。若在查询过程中遇到某个点在某张距离矩阵上的值为无穷大，则说明该点无法到达该房子，直接停止搜索即可。
4. 选3中距离最小的点即可。
【参考答案】
网友评论