给定源节点,dest节点和中间节点,如何检测最短的曼哈顿距离是否被阻止？

Question

这是我要发布的完整标题,但它恰好太长了:

给定源节点,dest节点和中间节点,如何检测中间节点是否阻塞了最短的曼哈顿距离？

我画了一个图表,使其更清晰.在左侧,"u"是源节点,"v"是目标节点.标记为1到6的节点是中间节点.距离u - > v的最短曼哈顿距离为12,但中间节点形成阻挡它的墙.右边的图表以u'为源,v'为目的地,表明中间节点1到5不会阻止从u'到v'的最短曼哈顿距离.

我正在尝试找到一种不需要我实际进行图搜索(例如BFS)的算法,因为u和v之间的距离可能非常大.

Answer 1

如果您想做的只是检测最短路径（由单调带您朝正确方向移动的移动组成的路径）是否被阻挡，那么您将尝试检查阻挡节点是否切割了其角点由源给出的矩形，并且目标节点进入两个断开连接的不同区域。如果从源到目的地不存在最短路径，则每条路径中都必须有某个点被阻塞。

为了简单起见，我们假设您的起点位于目的地点的左侧下方。在这种情况下，在 O(n) 中找到包含在包含起点和终点的边界框中的障碍点的所有其他点。现在，您想要查看这些节点中是否有某个子集将矩形切成两块，一块包含左下角，另一块包含右上角。如果存在从左侧到右侧、从左侧到底部、从顶部到右侧或从顶部到底部的阻塞节点的路径，则这是可能的。因此，我们只需要检查其中是否有可能。

幸运的是，这可以通过将问题建模为大小为 O(n) 的图中的图搜索来有效地完成，其中 n 是阻塞点的数量，与边界框的大小无关。也就是说，无论测试点相距多远，要搜索的图的大小仅取决于阻塞点的数量。

您要构建的图表有两部分。首先，构建一个图，其中每个阻塞点都与其周围 3x3 正方形中的每个其他阻塞点相连。这些边将可能属于同一屏障一部分的阻塞点连接在一起，因为从源到目标的路径不能在由边连接的两个阻塞点之间通过。现在，添加代表顶墙、左墙、右墙和底墙的四个新节点，并将它们连接到与相应墙相邻的每个节点。这样，例如，从左墙节点到右墙节点的路径将表示一系列阻塞节点，这些节点使得无法从左下节点到达右上节点。

该图的大小为 O(n)，其中 n 是阻塞节点的数量，因为有 O(n) 个节点，并且每个节点最多可以有 12 条边 - 8 个邻居中的每一个都有一条边，并且可能每个邻居都有一条边四堵墙。您可以通过扫描每个节点并对于每个其他节点查看它们是否相邻来在最坏的二次时间内构建它。可能有更好的方法来做到这一点，但目前我什么也没有想到。

现在您已经有了图形，对于每对墙（如果连接的话，将断开图形的连接），在此图形中的这两个墙节点之间运行图形搜索。如果路径存在，则报告最短路径被阻塞。如果没有，则报告某些最短路径已畅通。这些搜索可以使用简单的 DFS 来完成，或者由于您正在运行多个搜索并且只想知道它们是否连接，因此使用一次强连接组件算法并检查是否有任何一对重要节点位于同一 SCC 中。任何一种方法都需要时间 O(n)。

因此解决这个问题的时间最多是O(n ² )，瓶颈是构建图所需的时间。

希望这可以帮助！