2022-01-14：离建筑物最近的距离。 你是个房地产开发商，想要选择一片空地 建一栋大楼。你想把这栋大楼够造在一个距离周边设施都比较方便的地方，通过调研，你希望从它出发能在 最短的距离和 内抵达周边全部的建筑物。请你计算出这个最佳的选址到周边全部建筑物的 最短距离和。 注意： 你只能通过向上、下、左、右四个方向上移动。 给你一个由 0、1 和 2 组成的二维网格，其中： 0 代表你可以自由通过和选择建造的空地； 1 代表你无非通行的建筑物； 2 代表你无非通行的障碍物。 来自力扣317。

答案2022-01-14：

自然智慧即可。对每个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
}

执行结果如下： 图片

左神java代码