https://zhengyang2015.gitbooks.io/lintcode/build_post_office_573.html
http://www.jiuzhang.com/solutions/build-post-office/
http://www.jianshu.com/p/5395c7fe253f
设两个点：(x1,y1)、(x2,y2)
曼哈顿距离：dis=|x2-x1|+|y2-y1|
设两个点：(x1,y1)、(x2,y2)
曼哈顿距离：dis=|x2-x1|+|y2-y1|
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.)
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.)
这道题可以用dp来做，但是会超时。首先扫描一遍将所有house的点记录下来，然后遍历图中所有0的点，计算每个0的点到这些house的距离和，选最小的那个即可。这种情况下可以优化到O(k * n ^ 2)，但是如果数据量很大还是过不了。
因此需要减少搜索的点。想到的方法是在所有房子围成的形状的重心位置附近建邮局则到所有房子的距离之和最短（怎么证明？）。因此步骤如下：
- 首先找到所有房子的重心。找所有房子x值的median和y值的median（如果是奇数个就是排序后取中间值，如果是偶数则取中间两个数再取平均值）即为重心。
- 然后用bfs来搜索。将重心加入queue中，然后开始一圈一圈（将出队的每个点周围八个点加入队中）向外找，用的是和逐层遍历二叉树的类似的方法（即在每一层开始的时候记录一下本层的点的个数，然后一次出队这么多点即可将本层的点全部出队）。每一圈结束时，返回该圈上的点作为post office能取的最小值，如果存在则停止搜索。即如果存在可以作为post office的点，则外圈点到各个房子的距离一定不会比内圈点更优。
median version
class Node{
int x;
int y;
public Node(int x, int y){
this.x = x;
this.y = y;
}
}
int[] dx = {0, 0, -1, 1, -1, 1, -1, 1};
int[] dy = {-1, 1, 0, 0, -1, -1, 1, 1};
//Median version
public int shortestDistance(int[][] grid) {
// Write your code here
if(grid == null || grid.length == 0 || grid[0].length == 0){
return -1;
}
int n = grid.length;
int m = grid[0].length;
boolean[][] visit = new boolean[n][m];
ArrayList<Node> house = new ArrayList<Node>();
ArrayList<Integer> xArr = new ArrayList<Integer>();
ArrayList<Integer> yArr = new ArrayList<Integer>();
//find house position
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(grid[i][j] == 1){
house.add(new Node(i, j));
xArr.add(i);
yArr.add(j);
}
}
}
//no empty place
if(house.size() == m * n){
return -1;
}
if(house.size() == 0){
return 0;
}
//find the median of house positions
int xMedian = getMedian(xArr);
int yMedian = getMedian(yArr);
Queue<Node> queue = new LinkedList<Node>();
queue.add(new Node(xMedian, yMedian));
visit[xMedian][yMedian] = true;
int min = Integer.MAX_VALUE;
while(!queue.isEmpty()){
int size = queue.size();
for(int i = 0; i < size; i++){
Node curt = queue.poll();
if(grid[curt.x][curt.y] == 0){
min = Math.min(min, search(house, curt));
}
for(int j = 0; j < 8; j++){
int nextX = curt.x + dx[j];
int nextY = curt.y + dy[j];
if(nextX >= 0 && nextX < n && nextY >= 0 && nextY < m && !visit[nextX][nextY]){
visit[nextX][nextY] = true;
queue.add(new Node(nextX, nextY));
}
}
}
if(min != Integer.MAX_VALUE){
return min;
}
}
return -1;
}
private int getMedian(ArrayList<Integer> arr){
Collections.sort(arr);
int Median = arr.get(arr.size() / 2);
if(arr.size() % 2 == 0){
Median = (Median + arr.get(arr.size() / 2 - 1)) / 2;
}
return Median;
}
private int search(ArrayList<Node> house, Node curt){
int sum = 0;
for(Node node : house){
sum += Math.abs(curt.x - node.x) + Math.abs(curt.y - node.y);
}
return sum;
}http://www.jiuzhang.com/solutions/build-post-office/
http://www.jianshu.com/p/5395c7fe253f
这道题的要点就是distance可以直接用 x1-x2 + y1-y2求得，所以并不用搜索。做法还是先把所有房子存在一个数组里，然后对于每一个点，遍历房子数组，求total distance即可。
在该题设中，因为房子并不会充当一个阻碍物，所以并不需要用 BFS 等算法来计算最短路径，简单地计算两个格子之间在网格上的曼哈顿距离（Manhattan distance）就好了，即
最先想到的就是暴力算法：穷举网格上的每一个空地，并计算所有房子到它的距离，最后取最小的一个即可。实现起来就是几个嵌套循环，就此略过。最糟糕的情况下时间复杂度为。
如果我们进一步观察，可以发现，若我们在同一行上移动，所有房子（）到该行（）的垂直距离（Y 轴方向）不变，其和也因此不变，即 不变。同理，对于每一列也是如此。在同一列上移动，所有房子到该列的水平距离之和也不变。
充分利用上面的观察，我们就可以提出一个更好的算法，即先算出所有房子到每一行的距离之和以及每一列的距离之和，最后在网格上就可以很快的算出所有房子到某点的距离之和了。
想要算出所有房子到每一行或每一列的距离之和，我们可以进一步抽象，把问题转换成一维上的问题。以到每一行的距离之和为例。首先很直观就可以发现，对于任意两行上的点而言，其垂直距离都是固定不变的。于是我们可以进行水平方向的压缩（不需要水平坐标的信息了），即统计出每一行上的房子数目。而后，问题就变成了，在这个一维的线上算出所有点到任意一点的距离之和。利用前缀和（prefix sum），我们可以在的时间里解决。具体思路就是先从左边扫一遍，记录 范围内的点到 的距离之和，又是一个简单的动态规划了，其状态转移方程为
其中，
prefixSum[i]记录范围 之间点的个数。
类似的，再从右边扫一遍，记录 范围内的点到 的距离之和。最后把左右结果相加即可。
1. 因为这个题目要求无解的时候返回 -1 ，那么我们就先想一下无解的情况。
（1）网格不存在，即行数为0或者列数为0；
（2）网格存在，但是没有地方修，也就是没有空地。
（2）网格存在，但是没有地方修，也就是没有空地。
之后就要开始要想如何解决这个问题了。
2. 题目是要求所有的房子到某一空地的最小曼哈顿距离和，那我们就有一个朴素的想法，直接枚举所有的空地，求出所有的房子到该空地的曼哈顿距离和，从这些距离和中选取最小的一个即可。
（ps：曼哈顿距离：dis=|x2-x1|+|y2-y1|）
伪代码：
接下来就是改进这个朴素的做法。
3. 观察上述伪代码，显然求所有的房子到某一点的曼哈顿距离和是可以通过预处理实现O(1)询问的。
这里就要先提到有关曼哈顿距离的一个常用技巧了：将曼哈顿距离拆分成 X 轴距离与 Y 轴距离。
设两个点：(x1,y1)、(x2,y2)
曼哈顿距离：dis=|x2-x1|+|y2-y1|
根据上面这个式子，我们就可以把求两个点的曼哈顿距离拆分成求两个点在 X 轴上的距离与求两个点在 Y 轴上的距离。
有了这个拆分，就有了预处理的基础。
3. 观察上述伪代码，显然求所有的房子到某一点的曼哈顿距离和是可以通过预处理实现O(1)询问的。
这里就要先提到有关曼哈顿距离的一个常用技巧了：将曼哈顿距离拆分成 X 轴距离与 Y 轴距离。
设两个点：(x1,y1)、(x2,y2)
曼哈顿距离：dis=|x2-x1|+|y2-y1|
根据上面这个式子，我们就可以把求两个点的曼哈顿距离拆分成求两个点在 X 轴上的距离与求两个点在 Y 轴上的距离。
有了这个拆分，就有了预处理的基础。
4. 我们现在以对 X 轴距离做预处理为例进行讲解。
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 轴距离和，即得到下式：
用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 行的距离和，将其记为ansRow[i]。
综上，我们就可以通过O(row)的预处理得到所有房子到某一 行的距离和，并记录在ansRow[] 数组里。
5. 通过与第四点相同的思路，我们可以通过一个O(column)的预处理得到所有房子到某一列的距离和，并记录在ansColumn[] 数组里。
于是，所有房子到某一点(i,j)的曼哈顿距离和即为：ansRow[i] + ansColumn[j]。
代码的总体复杂度就下降到了O(row*column)。
代码的总体复杂度就下降到了O(row*column)。
如果这道题能够用bfs方法写出来可以达到hire的程度。如果能够优化，想到预处理的方法那么就可以拿到strong hire.
public int shortestDistance(int[][] grid) { // Write your code here int row = grid.length, column = grid[0].length; if(row == 0 || column == 0 || !haveZero(grid,row,column)) { return -1; } int[] rowSum = new int[row]; int[] columnSum = new int[column]; for(int i = 0; i < row; i++) for(int j = 0; j < column; j++) if(grid[i][j] == 1) { rowSum[i]++; columnSum[j]++; } int[] ansRow = new int[row]; int[] ansColumn = new int[column]; getSumDistance(rowSum,row,ansRow); getSumDistance(columnSum,column,ansColumn); int ans = Integer.MAX_VALUE; for(int i = 0; i < row; i++) for(int j = 0; j < column; j++) if(grid[i][j] == 0 && ans > ansRow[i] + ansColumn[j]) { ans = ansRow[i] + ansColumn[j]; } return ans; } void getSumDistance(int[] a,int n,int[] ans) { int[] prefixSum1 = new int[n]; int[] prefixSum2 = new int[n]; /* 第一阶段，处理前缀。 prefixSum1记录数组 a 的前缀和，即:prefixSum1[i]=a[0]+a[1]+..+a[i]. prefixSum2记录数组 prefixSum1 前缀和，prefixSum2即为前 i 个点到第 i 个点的代价和。 */ prefixSum1[0] = a[0]; for(int i = 1; i < n; i++) { prefixSum1[i] = prefixSum1[i - 1] + a[i]; } prefixSum2[0] = 0; for(int i = 1; i < n; i++) { prefixSum2[i] = prefixSum2[i - 1] + prefixSum1[i - 1]; } for(int i = 0; i < n; i++) { ans[i] = prefixSum2[i]; } /* 第二阶段，处理后缀。 prefixSum1记录数组 a 的后缀和，即:prefixSum1[i]=a[n-1]+a[n-2]+..+a[i]. prefixSum2记录数组 prefixSum1 的后缀和，prefixSum2即为 i 之后的点到第 i 个点的代价和。 */ prefixSum1[n - 1] = a[n - 1]; for(int i = n - 2; i >= 0; i--) { prefixSum1[i] = prefixSum1[i + 1] + a[i]; } prefixSum2[n - 1] =0; for(int i = n - 2; i >= 0; i--) { prefixSum2[i] = prefixSum2[i + 1] + prefixSum1[i + 1]; } for(int i = 0; i < n; i++) { ans[i] += prefixSum2[i]; } /* ans[i] 即为a数组中所有点到第 i 点的代价和 */ } boolean haveZero(int[][] grid, int row, int column) { for(int i = 0; i < row; i++) { for(int j = 0; j < column; j++){ if(grid[i][j] == 0) { return true; } } } return false; }
－Not efficient
public int shortestDistance(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) return -1;
ArrayList<Node> house = new ArrayList<>();
ArrayList<Node> empty = new ArrayList<>();
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 1) {
house.add(new Node(i, j));
}
else {
empty.add(new Node(i, j));
}
}
}
if (empty.size() == 0) return -1;
int min = Integer.MAX_VALUE;
for (Node node: empty) {
min = Math.min(min, helper(house, node));
}
return min;
}
private int helper(ArrayList<Node> house, Node node) {
int dist = 0;
for (Node cur: house) {
dist += Math.abs(cur.x - node.x) + Math.abs(cur.y - node.y);
}
return dist;
} int shortestDistance(vector<vector<int>>& grid) {
// Write your code here
if(grid.empty() || grid[0].empty()) return 0;
int row = grid.size(), col = grid[0].size();
vector<pair<int, int>> houses;
for(int i=0; i<row; i++){
for(int j=0; j<col; j++){
if(grid[i][j] == 1){
houses.push_back({i, j});
}
}
}
int ret = INT_MAX;
for(int i=0; i<row; i++){
for(int j=0; j<col; j++){
if(grid[i][j] == 0){
int dis = 0;
for(int k=0; k<houses.size(); k++){
dis += calculate(i, j, houses[k]);
}
ret = min(ret, dis);
}
}
}
return ret;
}
int calculate(int i, int j, pair<int, int> p){
return abs(i-p.first) + abs(j-p.second);
}