离建筑物最近的距离。
你是个房地产开发商，想要选择一片空地 建一栋大楼。你想把这栋大楼够造在一个距离周边设施都比较方便的地方，通过调研，你希望从它出发能在 最短的距离和 内抵达周边全部的建筑物。请你计算出这个最佳的选址到周边全部建筑物的 最短距离和。
注意：
你只能通过向上、下、左、右四个方向上移动。
给你一个由 0、1 和 2 组成的二维网格，其中：
0 代表你可以自由通过和选择建造的空地；
1 代表你无非通行的建筑物；
2 代表你无非通行的障碍物。
来自力扣317。
自然智慧即可。对每个1生成一个二维距离表。遍历所有二维表对应的点求和，对所有的和求最小值。
代码用golang编写。代码如下：
package main
import (
"fmt"
"math"
)
func main() {
grid := [][]int{{1, 0, 2, 0, 1}, {0, 0, 0, 0, 0}, {0, 0, 1, 0, 0}}
ret := shortestDistance3(grid)
fmt.Println(ret)
}
// 方法三的大流程和方法二完全一样，从每一个1出发，而不从0出发
// 运行时间快主要是因为常数优化，以下是优化点：
// 1) 宽度优先遍历时，一次解决一层，不是一个一个遍历：
// int size = que.size();
// level++;
// for (int k = 0; k < size; k++) { ... }
// 2) pass的值每次减1何用？只有之前所有的1都到达的0，才有必要继续尝试的意思
// 也就是说，如果某个1，自我封闭，之前的1根本到不了现在这个1附近的0，就没必要继续尝试了
// if (nextr >= 0 && nextr < grid.length
// && nextc >= 0 && nextc < grid[0].length
// && grid[nextr][nextc] == pass)
// 3) int[] trans = { 0, 1, 0, -1, 0 }; 的作用是迅速算出上、下、左、右
// 4) 如果某个1在计算时，它周围已经没有pass值了，可以提前宣告1之间是不连通的
// step = bfs(grid, dist, i, j, pass--, trans);
// if (step == Integer.MAX_VALUE) {
// return -1;
// }
// 5) 最要的优化，每个1到某个0的距离是逐渐叠加的，每个1给所有的0叠一次（宽度优先遍历）
// dist[nextr][nextc] += level;
func shortestDistance3(grid [][]int) int {
dist := make([][]int, len(grid))
for i := 0; i < len(dist); i++ {
dist[i] = make([]int, len(grid[0]))
}
pass := 0
step := math.MaxInt64
trans := []int{0, 1, 0, -1, 0}
for i := 0; i < len(grid); i++ {
for j := 0; j < len(grid[0]); j++ {
if grid[i][j] == 1 {
step = bfs(grid, dist, i, j, pass, trans)
pass--
if step == math.MaxInt64 {
return -1
}
}
}
}
if step == math.MaxInt64 {
return -1
} else {
return step
}
}
// 原始矩阵是grid，但是所有的路(0)，被改了
// 改成了啥？改成认为，pass才是路！原始矩阵中的1和2呢？不变！
// dist，距离压缩表，之前的bfs，也就是之前每个1，走到某个0，总距离和都在dist里
// row,col 宽度优先遍历的，出发点！
// trans -> 炫技的，上下左右
// 返回值代表，进行完这一遍bfs，压缩距离表中(dist)，最小值是谁？
// 如果突然发现，无法联通！返回系统最大！
func bfs(grid, dist [][]int, row, col, pass int, trans []int) int {
//Queue<int[]> que = new LinkedList<int[]>();
que := make([][]int, 0)
//que.offer(new int[] { row, col });
que = append(que, []int{row, col})
level := 0
ans := math.MaxInt64
for len(que) > 0 {
size := len(que)
level++
for k := 0; k < size; k++ {
//int[] node = que.poll();
node := que[0]
que = que[1:]
for i := 1; i < len(trans); i++ { // 上下左右
nextr := node[0] + trans[i-1]
nextc := node[1] + trans[i]
if nextr >= 0 && nextr < len(grid) && nextc >= 0 && nextc < len(grid[0]) && grid[nextr][nextc] == pass {
//que.offer(new int[] { nextr, nextc });
que = append(que, []int{nextr, nextc})
dist[nextr][nextc] += level
//ans = Math.min(ans, dist[nextr][nextc]);
if ans > dist[nextr][nextc] {
ans = dist[nextr][nextc]
}
grid[nextr][nextc]--
}
}
}
}
return ans
}执行结果如下：
