LeetCode 317. 离建筑物最近的距离
题目描述
题意分析
网格中的零表示可选空地，一表示已有建筑，二表示障碍。需要选一个空地作为建房位置，使它能到达全部建筑，并使到各栋建筑的最短距离之和尽可能小；不存在这样的空地时返回
-1。每步只能上下左右移动，途中只能经过空地，不能穿过障碍或其他建筑。求的是到所有建筑的距离总和，不是到最近建筑的距离，也不是各栋建筑间的距离。
解法：从每栋建筑分别 BFS 累加距离
核心思路
[!blue]
可以反过来从每栋建筑出发，为所有可到达空地计算距离。网格每步代价相同，用 BFS 按层扩展，某个空地第一次被发现时，就得到它到当前建筑的最短距离；路径反向仍然合法，因此正好是这个空地所需的一项距离。
对每个空地保存两个累计量：
distance是已经搜索过的建筑到它的最短距离总和，reach是其中能到达它的建筑数量。每栋建筑独立进行一次 BFS，将本轮贡献加入这两个矩阵。本轮的
seen必须重新创建，因为同一个空地需要分别接收不同建筑的距离，但不能在同一栋建筑的搜索里重复贡献。空地发现时立即标记再入队，避免同层多个方向把它重复加入。起点建筑在队列中对应距离零。代码的
steps从一开始，表示当前层节点新发现的空地距离；固定本层队列数量，只处理这批节点，下一批再把距离加一。其他建筑只作为各自搜索的起点，不能在当前搜索中进入并借道穿行。全部建筑完成后，只有
reach等于建筑总数的空地才是合法候选，再从中选最小距离和。部分可达的空地可能因为少算了一些建筑而看起来距离更小，不能参与比较。一次普通多源 BFS 只能得到每个格子到最近源的距离，不能代替逐建筑搜索后求和。这里需要为每个源分别保留它的最短距离贡献。
解题步骤
- 创建距离和矩阵、可达建筑数矩阵，统计搜索过的建筑数量。
- 遇到一栋建筑时，以它为起点创建独立队列和访问矩阵。
- 按层扩展，只进入界内、未访问的空地；入队时标记，并累加本轮距离和一次可达数量。
- 对所有建筑重复搜索，保留两个全局累计矩阵。
- 扫描空地，只比较可达所有建筑的位置；没有候选时返回负一。
代码实现
class Solution {
public int shortestDistance(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int buildings = 0;
int[][] distance = new int[m][n];
int[][] reach = new int[m][n];
int[] dirs = {
-1,
0,
1,
0,
-1
};
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] != 1) {
continue;
}
buildings++;
boolean[][] seen = new boolean[m][n];
Deque<int[]> queue = new ArrayDeque<>();
queue.add(new int[] {
r,
c
});
for (int steps = 1; !queue.isEmpty(); steps++) {
for (int size = queue.size(); size > 0; size--) {
int[] cell = queue.remove();
for (int d = 0; d < 4; d++) {
int x = cell[0] + dirs[d];
int y = cell[1] + dirs[d + 1];
if (x < 0
|| x >= m
|| y < 0
|| y >= n
|| grid[x][y] != 0
|| seen[x][y]) {
continue;
}
seen[x][y] = true;
distance[x][y] += steps;
reach[x][y]++;
queue.add(new int[] {
x,
y
});
}
}
}
}
}
int answer = Integer.MAX_VALUE;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == 0 && reach[r][c] == buildings) {
answer = Math.min(answer, distance[r][c]);
}
}
}
return answer == Integer.MAX_VALUE ? -1 : answer;
}
}
func shortestDistance(grid [][]int) int {
m, n := len(grid), len(grid[0])
buildings := 0
distance, reach := make([][]int, m), make([][]int, m)
for r := 0; r < m; r++ {
distance[r] = make([]int, n)
reach[r] = make([]int, n)
}
dirs := []int{
-1,
0,
1,
0,
-1,
}
for r := 0; r < m; r++ {
for c := 0; c < n; c++ {
if grid[r][c] != 1 {
continue
}
buildings++
seen := make([][]bool, m)
for i := range seen {
seen[i] = make([]bool, n)
}
queue := [][2]int{
{
r,
c,
},
}
head := 0
for steps := 1; head < len(queue); steps++ {
end := len(queue)
for head < end {
cell := queue[head]
head++
for d := 0; d < 4; d++ {
x, y := cell[0]+dirs[d], cell[1]+dirs[d+1]
if x < 0 || x >= m || y < 0 || y >= n || grid[x][y] != 0 || seen[x][y] {
continue
}
seen[x][y] = true
distance[x][y] += steps
reach[x][y]++
queue = append(queue, [2]int{
x,
y,
})
}
}
}
}
}
answer := -1
for r := 0; r < m; r++ {
for c := 0; c < n; c++ {
if grid[r][c] == 0 && reach[r][c] == buildings && (answer < 0 || distance[r][c] < answer) {
answer = distance[r][c]
}
}
}
return answer
}
复杂度分析
设网格有 $m$ 行、$n$ 列，建筑数量为 $B$。
- 时间复杂度：$O((B+1)mn)$，每栋建筑最多访问整个网格，另有最初扫描和最后筛选；存在建筑时通常写作 $O(Bmn)$。
- 辅助空间复杂度：$O(mn)$，两个累计矩阵以及每轮访问矩阵、队列；各轮搜索的临时状态可以被释放。
关键点总结
[!green]
- 单栋建筑的 BFS 提供最短距离，多栋建筑的结果按空地累加。
- 距离和必须搭配可达数量，才能排除未覆盖全部建筑的位置。
- 每栋建筑重置访问状态，每个空地在同一轮只贡献一次。
- 普通多源 BFS 求最近源，无法直接得到所有源距离之和。
易错点总结
[!yellow]
- 不能穿过其他建筑，它们不是本轮可扩展的空地。
- 访问标记不能跨建筑共享，否则后面的建筑无法再给同一空地贡献距离。
- 入队时就要标记，等到出队才标记可能导致重复入队和重复累计。
- BFS 层大小必须在本层开始时固定，新发现的空地属于下一层。
- 只看距离和而不检查
reach，会把只到达部分建筑的位置误选为最优。- 找不到可达全部建筑的空地时返回
-1，不是零或内部的大值哨兵。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 542. 01 矩阵 | 中等 | 都是网格 BFS，但多源搜索求最近源距离；本题必须分别求距后累加。 |
| 1091. 二进制矩阵中的最短路径 | 中等 | 复用障碍网格的最短路搜索；本题仅四方向，并要汇总到多个指定建筑的距离。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！