algorithm - 如何在这种迷宫中找到最短路径

Question

Red Dot - Represents the initial location
Black Dot - Already occupied
Green - Free to occupy
Destination - Boundry of the matrix [which means either x = 0 or y = 0 or x = 8 or y = 8]

示例:

红点 一次只能让自己移动一个，并且可以在附加到它的六个绿色圆圈之一中移动。在这种迷宫中计算最短路径的最快方法是什么。

Answer 1

首先，你不需要Dijkstra，因为边的所有值都是相同的。您可以使用简单的 BFS或 DFS算法。最坏情况的复杂度是相同的，但我会使用 BFS，因为它具有更好的平均情况复杂度。然而，O(|V|+|E|) 是最快的，并且已被证明。

如何表示您的图表？最好的方法是为每个 Node 保留一个邻居列表。您示例中的黑点不算作邻居。因此，在您的示例中，每个节点将有 0(完全被黑点覆盖)到 6 个邻居。然后，您可以通过这些列表从任何节点到达任何您可以到达的地方。

BFS 算法有一个属性，它为每个节点分配一个层，这意味着它与起始节点的距离。你从你的起点开始，你的当前层将为 0。然后你只需跟踪当前层的所有节点(通常保持在队列中)并尝试找到它的邻居(从他们的邻居列表中)，它没有层分配，你分配给他们 +1 更高层。一旦您在迷宫的边界找到您的节点(它仍然可以将 x,y 作为边界检查的属性(或属性 bool border))，您就知道它与您的图层值一样远。如果你想打印确切的方式，你只需要找到返回的方式(通过你的邻居列表)满足每一步都在 -1 层以下的条件。这将打印从头到尾的方式，但我相信在 Stack 数据结构的帮助下你会得到你的结果:)