LeetCode 317 Shortest Distance from All Buildings 详解空地到所有建筑的最短距离和多源 BFS 三解法与优化【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读本文以 articles/shortest-distance-from-all-buildings.md 为骨架系统讲解 LeetCode 317「从所有建筑物出发的最短距离」的完整解题体系在包含空地0、建筑1与障碍2的二维网格中找出一个空地使其到所有建筑的曼哈顿距离之和最小。读完本文你将掌握三类递进解法——从空地出发的单源 BFS、从房子出发的距离累积多源 BFS以及利用网格值递减替代 visited 数组的优化版多源 BFS并理解它们的时间/空间复杂度、适用场景与全部常见陷阱可直接迁移到仓库中其他网格 BFS 类问题如 腐烂的橘子、迷宫 II。一、问题定义与前置知识1.1 问题抽象输入是一个rows × cols的二维grid其中取值含义0空地可通行也是候选答案所在地1建筑房子不可通行但可作为 BFS 的源点或终点2障碍不可通行目标是找到一个空地单元格使它与每一栋建筑的路径长度之和最小若不存在能到达全部建筑的候选空地返回-1。移动规则为上下左右四方向每移动一格距离 1。1.2 前置技能清单原文档明确列出开始前需要具备的基础BFS广度优先搜索核心算法用于从某个源点求出到所有可达格子的最短距离天然保证「首次访问即最短」多源 BFS理解从多个起始点分别运行 BFS 并把距离结果累加到共享结构上的模式网格图遍历四方向移动、边界检查0 r rows 0 c cols、在二维矩阵中处理障碍距离累积跨多次 BFS 追踪累计距离与可达次数reachability count。这些前置能力也是仓库中 岛屿数量、被围绕的区域、岛屿的最大面积 等题解共用的基础。二、解法一从每个空地出发 BFS 到所有房子2.1 直觉对每一个空地格子我们想知道它到所有房子的距离之和。做法是对每个空地执行一次 BFS求出到每栋房子的最短路径。如果某个空地无法到达所有房子就把它标记为“阻塞”避免后续迭代重复检查它。原文档指出当房子多而空地少时此方案表现更好因为 BFS 的次数由空地数量决定。2.2 算法步骤统计网格中房子的总数total_houses对每个值为0的空地执行 BFS求它到所有可达房子的最短距离累加距离之和并计数到达的房子数若未到达全部房子则把本次 BFS 访问过的所有空地改写为2视为障碍用于剪枝后续搜索否则用该距离和更新全局最小值返回最小距离若不存在任何有效空地返回-1。2.3 Python 实现核心逻辑class Solution: def shortestDistance(self, grid: List[List[int]]) - int: rows, cols len(grid), len(grid[0]) dirs [(1, 0), (-1, 0), (0, 1), (0, -1)] total_houses 0 for row in range(rows): for col in range(cols): if grid[row][col] 1: total_houses 1 def bfs(start_row, start_col): distance_sum 0 houses_reached 0 q deque([(start_row, start_col)]) vis [[False] * cols for _ in range(rows)] vis[start_row][start_col] True steps 0 while q and houses_reached ! total_houses: for _ in range(len(q)): row, col q.popleft() if grid[row][col] 1: distance_sum steps houses_reached 1 continue # 房子不可继续通行 for dr, dc in dirs: next_row, next_col row dr, col dc if 0 next_row rows and 0 next_col cols: if not vis[next_row][next_col] and grid[next_row][next_col] ! 2: vis[next_row][next_col] True q.append((next_row, next_col)) steps 1 if houses_reached ! total_houses: # 本 BFS 访问过的空地同样无法到达全部房子标记为障碍以剪枝 for row in range(rows): for col in range(cols): if grid[row][col] 0 and vis[row][col]: grid[row][col] 2 return float(inf) return distance_sum min_distance float(inf) for row in range(rows): for col in range(cols): if grid[row][col] 0: min_distance min(min_distance, bfs(row, col)) return -1 if min_distance float(inf) else min_distance2.4 关键细节剖析按层计数距离for _ in range(len(q))内层循环完整遍历当前层steps每处理完一层 1保证「遇到房子时steps即为从源点出发的最短步数」遇到房子即continue房子不可通行因此不把房子加入下一层队列剪枝的正确性若从某空地出发无法到达全部房子则本次访问过的所有空地也必然无法到达全部房子它们与这栋不可达的房子之间隔着相同的障碍因此可安全改写为2多语言对照原文档同时给出了 Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust 八个版本的等价实现例如 Java 用Queueint[] q new LinkedList()C 用queuepairint,intJavaScript 使用datastructures-js/queue的QueueGo 用q append(q, ...)模拟队列Rust 用VecDeque(usize, usize)。2.5 复杂度时间复杂度$O(N^2 \cdot M^2)$空间复杂度$O(N \cdot M)$其中 $N$、$M$ 分别为网格行数与列数。最坏情况下每个空地都做一次全网格 BFS。三、解法二从每个房子出发 BFS把距离累积到空地3.1 直觉把搜索方向反过来从每栋房子出发做 BFS得到该房子到所有可达空地的距离并把这些距离累加到一张独立的矩阵中。同时为每个空地记录「有多少栋房子能到达它」只有被所有房子到达的空地才是合法候选。3.2 算法步骤建立distances矩阵每个格子存[total_distance, house_count]二元组对每个房子值为1执行 BFS 到所有可达空地对每个访问到的空地把距离加到其累计值并把其房子计数 1处理完所有房子后扫描网格找出house_count total_houses的空地返回其中累计距离最小的若没有合法空地返回-1。3.3 Python 实现核心逻辑class Solution: def shortestDistance(self, grid: List[List[int]]) - int: rows, cols len(grid), len(grid[0]) dirs [(1, 0), (-1, 0), (0, 1), (0, -1)] total_houses 0 # 每个格子记录 [累计距离, 可达房子数] distances [[[0, 0] for _ in range(cols)] for _ in range(rows)] def bfs(start_row, start_col): q deque([(start_row, start_col)]) vis [[False] * cols for _ in range(rows)] vis[start_row][start_col] True steps 0 while q: for _ in range(len(q)): row, col q.popleft() if grid[row][col] 0: distances[row][col][0] steps distances[row][col][1] 1 for dr, dc in dirs: next_row, next_col row dr, col dc if 0 next_row rows and 0 next_col cols: if not vis[next_row][next_col] and grid[next_row][next_col] 0: vis[next_row][next_col] True q.append((next_row, next_col)) steps 1 for row in range(rows): for col in range(cols): if grid[row][col] 1: total_houses 1 bfs(row, col) min_distance float(inf) for row in range(rows): for col in range(cols): if distances[row][col][1] total_houses: min_distance min(min_distance, distances[row][col][0]) return -1 if min_distance float(inf) else min_distance3.4 关键细节剖析只向空地扩散BFS 的下一层只接受值为0的格子grid[next_row][next_col] 0障碍与房子都不再扩展可达性用计数表达house_count字段替代了解法一中“改写为障碍”的破坏性操作原网格grid始终保持不变这是与解法三的重要区别多语言实现Java 用int[][][] distances new int[rows][cols][2]存储二元组C 用vectorvectorvectorintRust 用vec![vec![[0i32, 0i32]; cols]; rows]Swift 用[[[Int]]]核心逻辑完全一致。3.5 复杂度时间复杂度$O(N^2 \cdot M^2)$空间复杂度$O(N \cdot M)$相比解法一此法不修改原网格代价是多维护了一个distances累积矩阵。四、解法三从房子出发的优化版——用网格值递减替代 visited 数组4.1 核心洞察解法二每次 BFS 都要新建 visited 数组还要用house_count校验可达性。优化版的关键洞察是直接把网格值本身当作访问标记。初始时空地值为0第一栋房子的 BFS 结束后所有可达空地被减 1 变成-1第二栋房子的 BFS 只访问值为-1的格子即可被恰好一栋房子到达的格子并把它们减为-2依此类推。第 $k$ 栋房子只访问值为-(k-1)$ 的格子把其减为-k天然地剪掉了那些被某栋房子挡住的不可达区域。这样既省掉了visited数组也省掉了房子计数一个空地的值最终等于-total_houses就说明它被所有房子到达过。4.2 算法步骤创建total矩阵用于累积每个空地的距离和初始化emptyLandValue 0对每栋房子执行 BFS只访问值等于emptyLandValue的格子对每个访问到的格子距离累加到total格子值减 1在本次 BFS 访问到的格子中跟踪最小累计距离迭代结束后emptyLandValue - 1返回最小距离若无合法空地返回-1。4.3 Python 实现核心逻辑class Solution: def shortestDistance(self, grid: List[List[int]]) - int: dirs [[1, 0], [-1, 0], [0, 1], [0, -1]] rows len(grid) cols len(grid[0]) # total 矩阵累积每个空地的距离总和 total [[0] * cols for _ in range(rows)] empty_land_value 0 min_dist float(inf) for row in range(rows): for col in range(cols): if grid[row][col] 1: # 从每栋房子出发 BFS min_dist float(inf) q deque([(row, col)]) steps 0 while q: steps 1 level_size len(q) for level in range(level_size): curr q.popleft() for dr, dc in dirs: next_row curr[0] dr next_col curr[1] dc # 只访问值等于 empty_land_value 的格子 if (0 next_row rows and 0 next_col cols and grid[next_row][next_col] empty_land_value): grid[next_row][next_col] - 1 total[next_row][next_col] steps q.append((next_row, next_col)) min_dist min(min_dist, total[next_row][next_col]) # 下一次迭代搜索的值整体下移 empty_land_value - 1 return -1 if min_dist float(inf) else min_dist4.4 为什么值匹配就能保证正确第 1 栋房子只访问值为0的空地emptyLandValue 0将其变为-1被障碍隔断、第 1 栋房子到不了的空地仍为0第 2 栋房子只访问值为-1的空地emptyLandValue -1将其变为-2。那些值为0的格子第 1 栋房子到不了不会被访问从而在后续所有迭代中被自然剪枝第 $k$ 栋房子只访问值为-(k-1)$ 的格子将其变为-k$。最终值为-total_houses的空地即被所有房子到达障碍2与房子1的值永远不会等于emptyLandValue它从 0 向下递减因此天然不可通行无需单独判断。4.5 复杂度与收益时间复杂度$O(N^2 \cdot M^2)$空间复杂度$O(N \cdot M)$与原文档标注一致。虽然渐进复杂度与解法二相同但省掉了每次 BFS 重建 visited 数组的开销与房子计数的校验逻辑常数因子显著更小是面试中最推荐的实现。多语言对照Java 版本用grid[nextRow][nextCol]--就地递减C 版本在边界判断中叠加grid[nextRow][nextCol] emptyLandValue条件Go 版本用grid[nextRow][nextCol]--与total[nextRow][nextCol] stepsRust 版本因所有权需将grid声明为mut。全部等价实现均可在原文档 articles/shortest-distance-from-all-buildings.md 中查阅。五、三种解法对比与选择维度解法一空地出发解法二房子出发解法三房子出发优化BFS 次数空地数房子数房子数是否修改原网格是将不可达空地改写为 2否是空地值递减为负数visited 数组每次 BFS 新建每次 BFS 新建不需要可达性判定与total_houses比对house_count计数值等于-total_houses时间$O(N^2M^2)$$O(N^2M^2)$$O(N^2M^2)$空间$O(NM)$$O(NM)$$O(NM)$适用场景空地少、房子多房子少、空地多通用常数最优选择依据若房子数量远少于空地数量从房子出发解法二/三能显著减少 BFS 次数若相反则从空地出发解法一更划算。解法三在两者之间综合最优是实际编码的首选。六、常见陷阱原文档完整收录6.1 未检查“能否到达所有房子”空地只有在能到达所有房子时才合法。只求最小距离和是不够的——还必须验证该空地能到达每一栋房子。无法到达全部房子的单元格必须被排除否则若不存在合法空地结果应为-1。解法一中houses_reached ! total_houses的判定、解法二中house_count total_houses的筛选、解法三中min_dist保持inf的兜底都是在落实这条规则。6.2 错误的提前终止有些实现试图在“遇到一栋房子”时提前结束 BFS 以优化性能。但若采用从房子出发的策略BFS 必须继续扩展到所有可达空地才能正确累积距离。提前终止会导致距离和不完整、结果错误。6.3 修改网格时未同步跟踪可达性优化版用递减值0、-1、-2、…标记“被此前所有房子到达过”的格子。常见错误是没理解值为k的格子只能被第(|k|1)栋房子的 BFS 访问。值与预期不符的格子要么是障碍、房子要么是某栋房子到达不了的区域不应入队。6.4 混淆两种 BFS 方向两种合法思路是从空地出发 BFS 到房子或从房子出发 BFS 到空地。把两者概念混用会导致逻辑错误——从房子出发时每栋房子的 BFS 把距离贡献给空地从空地出发时每个空地计算到所有房子的总距离。务必在一份代码中只坚持一种方向。6.5 距离求和的整数溢出在大网格且房子很多时距离和可能非常大。若用Integer.MAX_VALUE或float(inf)、INT_MAX、math.MaxInt32等作为无效格子的哨兵值再对其做算术运算可能发生溢出。应确保比较时跳过哨兵值绝不把距离累加到哨兵上。七、延伸阅读本题所依赖的网格 BFS、多源 BFS 与距离累积技巧在仓库中有多篇可直接对照的主题文档腐烂的橘子经典多源 BFS 分层扩散示例迷宫 II网格中最短路径距离的另一种 BFS 变体岛屿与宝藏多源 BFS 求各点到最近源点距离岛屿数量、被围绕的区域、岛屿的最大面积网格四方向遍历与连通性基础单词接龙BFS 从图论网格迁移到抽象图的实战案例。此外仓库的 hints 目录收录了多道题目的提示卡片可作为刷题路径的补充索引。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考