LeetCode 317 最短距离选址问题详解（Swift 实现 + BFS 多源遍历）

摘要

如果你在城市规划系统里工作，或者搞一个模拟经营类游戏，那你肯定遇到过这样的需求：找一个最优位置建房子，让它到所有已有建筑的总距离最短。

LeetCode 317 就是这么一道“建房选址”的题，表面是 BFS 遍历地图，实际是一个网格图上的多源路径搜索 + 最小和策略的组合题。

这篇文章用 Swift 带你分析如何高效地选出“最适合造房子”的格子位置，既有运行逻辑讲解，也有完整 Demo 和测试案例，适合用来刷题、面试、或做模拟业务模型的参考。

描述

题目是这样说的：

给你一个 m x n 的网格地图 grid，每个格子可能是：

• 0：空地，可以建房子
• 1：建筑，不能通过
• 2：障碍物，不能通过

你需要从这些空地中选一个点建房子，要求：

该点到所有建筑的曼哈顿距离之和最小

如果不存在这样的位置可以访问所有建筑，则返回 -1。

示例 1：

输入：
[[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]输出：
7解释：
选中 [1,2] 这个位置，到三个建筑的距离是：
(1,2) -> (0,0): 3
(1,2) -> (0,4): 3
(1,2) -> (2,2): 1
总和为 7，是所有可选位置中最小的。

题解答案

为了找出一个“能到所有建筑”的空地，并且使得总路径最短，我们可以反向思考：

遍历方式：

• 不是从空地出发去看能到哪些建筑。

• 而是从每一栋建筑出发去 BFS 扫空地，记录每个空地的：

  • 累计路径总和（sumDistance）
  • 被访问建筑数量（reachCount）

最后检查哪些空地被所有建筑都访问到，再从这些里选一个总距离最小的。

题解代码分析（Swift 实现）

func shortestDistance(_ grid: [[Int]]) -> Int {let rows = grid.countlet cols = grid[0].countvar distanceSum = Array(repeating: Array(repeating: 0, count: cols), count: rows)var reachCount = Array(repeating: Array(repeating: 0, count: cols), count: rows)let directions = [(-1,0), (1,0), (0,-1), (0,1)]var totalBuildings = 0for i in 0..<rows {for j in 0..<cols {if grid[i][j] == 1 {totalBuildings += 1bfs(i, j, grid, &distanceSum, &reachCount, rows, cols, directions)}}}var minDist = Int.maxfor i in 0..<rows {for j in 0..<cols {if grid[i][j] == 0 && reachCount[i][j] == totalBuildings {minDist = min(minDist, distanceSum[i][j])}}}return minDist == Int.max ? -1 : minDist
}func bfs(_ row: Int, _ col: Int, _ grid: [[Int]],_ distanceSum: inout [[Int]],_ reachCount: inout [[Int]],_ rows: Int, _ cols: Int,_ directions: [(Int, Int)]) {var visited = Array(repeating: Array(repeating: false, count: cols), count: rows)var queue: [(Int, Int, Int)] = [(row, col, 0)]visited[row][col] = truewhile !queue.isEmpty {let (x, y, dist) = queue.removeFirst()for (dx, dy) in directions {let newX = x + dxlet newY = y + dyif newX >= 0, newX < rows, newY >= 0, newY < cols,!visited[newX][newY], grid[newX][newY] == 0 {visited[newX][newY] = truedistanceSum[newX][newY] += dist + 1reachCount[newX][newY] += 1queue.append((newX, newY, dist + 1))}}}
}

题解代码解析

核心结构

• distanceSum[i][j]: 表示空地 (i, j) 到所有建筑的距离之和；
• reachCount[i][j]: 表示这个空地目前能被多少个建筑访问到；
• bfs()：从每一栋建筑出发，把可以走到的空地进行更新。

遍历每一栋建筑

if grid[i][j] == 1 {bfs(i, j, ...)
}

每次都从建筑出发跑一轮 BFS，让这栋建筑“把它能访问的空地都更新一遍”。

BFS 细节逻辑

• 维护一个 visited 数组防止重复遍历；

• 遇到空地就：

  • 更新它的 distanceSum 累加路径长度；
  • 更新它的 reachCount 加 1；
  • 加入下一轮队列。

最后从所有“被所有建筑都访问过的空地”中选出最小距离：

if reachCount[i][j] == totalBuildings

这句话的意思是，这块空地被所有建筑都走到过，才是合法候选地。

示例测试及结果

我们来验证下主例题：

let input = [[1, 0, 2, 0, 1],[0, 0, 0, 0, 0],[0, 0, 1, 0, 0]
]
let result = shortestDistance(input)
print(result)  // 输出：7

解释：

选中 [1,2] 位置，离三栋建筑的距离为：3 + 3 + 1 = 7
而其他空地虽然能访问一部分建筑，但总距离更大或不满足“可达所有建筑”的条件。

时间复杂度

• 对于每个建筑（共 b 个），执行一次 BFS；
• 每次 BFS 最多遍历所有空地（最多 m * n 个）；

所以总时间复杂度是 O(b × m × n)，对于题目给定的规模是可以接受的。

空间复杂度

• distanceSum、reachCount 和 visited 都是 m x n 的二维数组；
• 每次 BFS 使用的队列空间也最多为 O(mn)。

所以整体空间复杂度为 O(m × n)。

总结

LeetCode 317 是一道典型的“网格图上多源最短路径累加”问题，技巧核心是：

• 多次从“源点”出发进行 BFS；
• 用额外数组记录“累加状态”和“覆盖次数”；
• 最后从所有可选项中选最优解。

实际应用场景：

• 城市交通：选择公交站点或医院位置；
• 游戏地图：找玩家基地或资源点的最优投放位置；
• 后端服务部署：计算请求源覆盖范围、延迟等指标汇总选址；