网格基地选址优化：最小化兴趣点往返总路程的高效解法问询

你的原解法逻辑正确，但未利用题目中k远小于m×n的关键条件，导致时间复杂度偏高。优化核心是反向遍历：从每个POI出发做BFS，而非从每个候选基地出发，具体步骤如下：

步骤1：初始化距离存储结构 #

创建一个二维数组（维度为m×n），每个元素是长度为k的数组，初始值设为-1（表示不可达）。该结构用于记录网格中每个可通行格子到每一个POI的最短距离。

步骤2：对每个POI执行BFS #

遍历每一个POI：

• 以当前POI为起点，执行广度优先搜索（BFS）——由于仅允许上下左右移动，BFS可保证得到最短路径。
• 遍历过程中跳过标记为X的不可通行格子，将每个可通行格子（-或P）到当前POI的距离，更新到对应存储位置中。

步骤3：筛选最优基地 #

遍历网格中所有可通行格子：

• 检查该格子是否能到达所有POI（即对应k个距离值均不为-1）。
• 若满足条件，计算该格子到所有POI的距离之和，总往返路程为该和的2倍。
• 记录所有符合条件的格子中，总路程最小的那些格子。

复杂度对比 #

• 原解法时间复杂度：O((m×n)²)，每个候选基地需做一次O(mn)的BFS，共mn个候选。
• 优化后时间复杂度：O(k×m×n)，仅需k次O(mn)的BFS，因k远小于mn，效率提升显著。

示例验证 #

以题目中的示例网格为例：

X X X X X X
X P - - P X
X X X X X X

1. 对第一个P（第二行第二列）做BFS，得到各可通行格子的距离：自身0，右侧两个-分别为1、2，第二个P为3。
2. 对第二个P（第二行第五列）做BFS，得到各可通行格子的距离：自身0，左侧两个-分别为1、2，第一个P为3。
3. 计算每个可通行格子的距离和：
   • 第一个P：0+3=3 → 总路程6
   • 第一个-：1+2=3 → 总路程6
   • 第二个-：2+1=3 → 总路程6
   • 第二个P：3+0=3 → 总路程6
     这四个格子均符合条件，总路程均为6，与题目给出的合法答案一致。

内容的提问来源于stack exchange，提问作者user21200640