http://www.cnblogs.com/aprilyang/p/6507928.html
https://zhengyang2015.gitbooks.io/lintcode/build_post_office_ii_573.html
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
- You cannot pass through wall and house, but can pass through empty.
- 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.)
Challenge
Solve this problem within
O(n^3) time.
This problem can use reverse bfs. We can think about a problem in a reverse way. Since house number is much smaller than empty spaces we use house to bfs, which will be more efficient.
Notice that we need a matrix to record which one is visited and how many times there are. And another matrix to record how many stepts are needed to get that point. In the end, find one point that is visited the number of house times and have the minimum steps.
public int shortestDistance(int[][] grid) { if (grid == null || grid.length == 0 || grid[0].length == 0) { return -1; } int n = grid.length; int m = grid[0].length; int[][] visitedTimes = new int[n][m]; int[][] steps = new int[n][m]; ArrayList<Coordinate> houses = new ArrayList<>(); ArrayList<Coordinate> empty = new ArrayList<>(); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (grid[i][j] == 0) { empty.add(new Coordinate(i, j)); } if (grid[i][j] == 1) { houses.add(new Coordinate(i, j)); } } } for (Coordinate house : houses) { bfs(grid, house, visitedTimes, steps); } int min = Integer.MAX_VALUE; int houseNumber = houses.size(); for (Coordinate p: empty) { int x = p.x; int y = p.y; if (visitedTimes[x][y] == houseNumber) { if (steps[x][y] != 0 && steps[x][y] < min) { min = steps[x][y]; } } } return min == Integer.MAX_VALUE ? -1 : min; } public void bfs(int[][] grid, Coordinate point, int[][] visitedTimes, int[][] steps) { int[] dx = {0, 0, 1, -1}; int[] dy = {1, -1, 0, 0}; Queue<Coordinate> q = new LinkedList<>(); boolean[][] visited = new boolean[grid.length][grid[0].length]; q.add(point); int step = 0; while (!q.isEmpty()) { int size = q.size(); step++; for (int i = 0; i < size; i++) { Coordinate house = q.poll(); for (int j = 0; j < 4; j++) { int x = house.x + dx[j]; int y = house.y + dy[j]; Coordinate nextHouse = new Coordinate(x, y); if (isValid(grid, nextHouse) && !visited[x][y]) { steps[x][y] += step; visitedTimes[x][y]++; q.offer(nextHouse); visited[x][y] = true; } } } } } private boolean isValid(int[][] grid, Coordinate point) { int x = point.x; int y = point.y; return x >= 0 && y >= 0 && x < grid.length && y < grid[0].length && grid[x][y] == 0; }
https://zhengyang2015.gitbooks.io/lintcode/build_post_office_ii_573.html
这道题和I比较类似，但是因为不能穿过wall和house，所以必须用bfs的方法搜索最近距离，而不能直接计算几何距离。
- 将数组扫描一遍找到所有房子。
- 为每一个房子建立一个距离矩阵，计算该房子到所有0点的距离。即distance[i][j][k]为k房子到grid[i][j]上的点的距离。计算距离的时候用bfs搜索。
- 然后遍历图上所有为0的点，查询k张距离矩阵，将所有房子到该点的距离加起来即为在该点建邮局的距离总和。若在查询过程中遇到某个点在某张距离矩阵上的值为无穷大，则说明该点无法到达该房子，直接停止搜索即可。
- 选3中距离最小的点即可。
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;
ArrayList<Node> house = new ArrayList<Node>();
//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, 0));
}
}
}
//no empty place
int k = house.size();
if(k == n * m){
return -1;
}
int[][][] distance = new int[k][n][m];
for(int i = 0; i < k; i++){
for(int j = 0; j < n; j++){
Arrays.fill(distance[i][j], Integer.MAX_VALUE);
}
}
for(int i = 0; i < k; i++){
getDistance(house.get(i), distance, i, grid);
}
int min = Integer.MAX_VALUE;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(grid[i][j] == 0){
int sum = 0;
for(int l = 0; l < k; l++){
if(distance[l][i][j] == Integer.MAX_VALUE){
sum = Integer.MAX_VALUE;
break;
}
sum += distance[l][i][j];
}
min = Math.min(min, sum);
}
}
}
if(min == Integer.MAX_VALUE){
return -1;
}
return min;
}
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
//BFS search for shortest path
private void getDistance(Node curt, int[][][] distance, int k, int[][] grid){
int n = grid.length;
int m = grid[0].length;
Queue<Node> queue = new LinkedList<Node>();
boolean[][] visited = new boolean[n][m];
queue.offer(curt);
visited[curt.x][curt.y] = true;
while(!queue.isEmpty()){
Node now = queue.poll();
for(int i = 0; i < 4; i++){
int nextX = now.x + dx[i];
int nextY = now.y + dy[i];
if(nextX >= 0 && nextX < n && nextY >= 0 && nextY < m && grid[nextX][nextY] == 0 && !visited[nextX][nextY]){
distance[k][nextX][nextY] = now.dis + 1;
queue.add(new Node(nextX, nextY, now.dis + 1));
visited[nextX][nextY] = true;
}
}
}
}
作为上一题的变形，在这一题的题设中，这里的网格多了一种类型 - 墙
2，而且房子也被当做障碍物处理，即不能通过。这样的话，我们就不能利用上一题的解法，而要采用图论中的最短路径解法了，BFS 就是一种常用的选择。
同样，最开始能够想到的也是暴力算法，即穷举每一块空地，然后用 BFS 算一下到所有房子的距离，代码实现起来也不难，就略过了。
但是这里还有另外一个角度来思考这个问题，即从房子的角度来看。也是用 BFS 来遍历所有的空地，不过这里就需要在每个空地中记录房子访问次数和房子距离之和了。记录访问次数是为了确保所有房子都能访问到该空地，否则就不是可行解。这种解法的优势是在于当房子数目远小于空地数目时比上面从空地出发进行 BFS 要更快一些。所以这也是一种权衡（trade-off）了，要视数据集的具体情况而定。
