这道题给定一个二维网格:表示空地,表示建筑物,表示障碍物。只能上下左右移动,需要找一块空地,使它到所有建筑物的最短距离之和最小。如果没有任何空地能到达所有建筑物,返回 -1。
基础做法是从每栋建筑物分别做 BFS,把它到各个空地的最短距离累加起来。进一步优化时,可以利用网格值做递减标记,提前排除那些无法被此前所有建筑物到达的空地。
基础思路:从每栋建筑物进行 BFS
对每栋建筑物启动一次 BFS。每当首次到达一块空地,就把当前建筑到它的距离加到 dist[row][col]。
BFS 按距离逐被所有建筑到达,再讲逐栋 BFS 如何累加距离,接着解释递减标记如何筛掉不完整候选,最后补充无建筑、无空地、不可达和输入被修改等边界。
专注技术岗位的 VO 面试支持,覆盖 Coding、System Design、Behavioral / BQ 和 Project Deep Dive 等环节。如果你正在准备技术面试,欢迎来聊~
|