algorithm - 这两个广度优先搜索问题有何不同

Question

下面是两个广度优先搜索遍历问题。

问题 1:317 - 距所有建筑物的最短距离

这个问题的解决方法是从每个建筑物做广度优先搜索遍历，记录从它到可达单元格的距离。 最短距离是从每个建筑物可到达的小区，并且具有从每个建筑物到达该小区的距离的累积最短距离。

问题 2:296 - 最佳汇合点 我发现这道题和前面的一模一样，只是这里没有2，也就是障碍物。为什么会有不同的解决方案？

我试图了解这两个问题之间的区别，以及为什么第一个问题的解决方案不适用于第二个问题。曼哈顿距离与它有什么关系吗？

编辑:根据下面 SimMac 的回答，我尝试更新曼哈顿和从位于 (0,1) 的建筑物开始的行驶距离。输入以及曼哈顿和行驶距离如下。 SimMac，请你验证这些。

Input
0 - 1 - 2 - 0 - 1
|   |   |   |   |
0 - 2 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 0 - 0 - 1


Manhattan distance
1 - source - INF - 8 -   9
|      |     |     |     |
2 -   INF -  6 -   7 -   8
|      |     |     |     |
3 -    4 -   5 -   6 -   7

Travelling Distance
1-   source- INF - INF - INF
|      |     |     |     |
2 -   INF - INF - INF - INF
|      |     |     |     |
3 -   INF - INF - INF - INF

Answer 1

您可以对第二个问题使用第一个算法，但这不是必需的。

您已经提到了曼哈顿距离。您现在可以简单地计算曼哈顿距离并使用该值，而不是通过 BFS 来计算两点之间的距离。因为两点 (x1, y1), (x2, y2) 之间的曼哈顿距离只是 x1 和 x2 的绝对差加上 y1 和 y2 的绝对差，所以用这种方式计算距离要快得多。

你不能在第一个问题上使用曼哈顿距离，因为你可能会遇到这样的情况:

0 - 1 - 2 - 0 - 1
|   |   |   |   |
0 - 2 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 0 - 0 - 1

您可以轻松地看到从 (0,1) 处的建筑物到不在最右列中的任何点的行进距离与曼哈顿距离有何不同。

让我们画出从建筑物到其他所有领域的行进距离:

1 - x - + - 8 - 9
|   |   |   |   |
2 - + - 6 - 7 - 8
|   |   |   |   |
3 - 4 - 5 - 6 - 7

曼哈顿距离看起来像这样(不受障碍物影响):

1 - x - + - 2 - 3
|   |   |   |   |
2 - + - 2 - 3 - 4
|   |   |   |   |
3 - 2 - 3 - 4 - 5