我在编码面试中收到了这个面试问题：
你正在访问一个表面由 m x n 网格表示的行星。在这个网格上，有 k 个兴趣点以及不可穿越的瓦片。你需要找到最好的瓷砖来放置你的行动基地，你需要从那里访问每个兴趣点，每次你访问一个兴趣点你需要回到你的行动基地，目标是放置基地这样总的行程距离是最小的。你只能上下左右移动。每个兴趣点都可以从其他所有兴趣点到达，但并不是网格上的每个瓦片都可以从其他瓦片到达。同样，数字 k 明显小于 m x n
例如，如果你有网格：
X X X X X X X P - - P X X X X X X X
一个有效的答案是第二行和第一列和最后一列之间的任何方块，因为总行程距离为 6 以访问所有兴趣点并返回基地。
瓦片可以放置在值为连字符（可以遍历但不是兴趣点）或“P”（可以遍历并且是兴趣点）的位置。带有“X”的方块不可遍历。
我的解决方案：
对于每个候选点，对所有感兴趣的点进行广度优先搜索。候选点的总距离是它到每个点的距离的两倍。然后我返回了（1）可以访问所有兴趣点并且（2）具有最小总旅行距离的候选点。
面试官说这个解决方案有效，但表示可以通过使用来自兴趣点的数据更有效地计算“-”点的距离。我被卡住了，不知道该怎么做。
我认为使用记忆化或动态编程方法可能是正确的解决方案，但不知道如何提出解决方案。
我认为你的解决方案是 O(nmck)，其中 c 是候选人的数量。您可以将其减少到 O(nmk)，如下所示：
对于每个兴趣点，计算到每个可到达点的最短距离。总结每个点的距离，然后扫描最小值（在候选点中）。如果您想知道实际距离，则必须乘以二，因为这只会以一种方式计算到每个兴趣点的距离。
所以基本上你几乎做对了所有事情，只是在错误的一端开始搜索。