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代码