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

在这里插入图片描述

文章目录

摘要

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

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.count
    let cols = grid[0].count
    var 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 = 0

    for i in 0..<rows {
        for j in 0..<cols {
            if grid[i][j] == 1 {
                totalBuildings += 1
                bfs(i, j, grid, &distanceSum, &reachCount, rows, cols, directions)
            }
        }
    }

    var minDist = Int.max
    for 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] = true

    while !queue.isEmpty {
        let (x, y, dist) = queue.removeFirst()
        for (dx, dy) in directions {
            let newX = x + dx
            let newY = y + dy

            if newX >= 0, newX < rows, newY >= 0, newY < cols,
               !visited[newX][newY], grid[newX][newY] == 0 {
                visited[newX][newY] = true
                distanceSum[newX][newY] += dist + 1
                reachCount[newX][newY] += 1
                queue.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；
用额外数组记录“累加状态”和“覆盖次数”；
最后从所有可选项中选最优解。

实际应用场景：

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

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