如何在这种类型的迷宫中寻找最短路径

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]

例:

它red dot可以一次只放置一个动作,并且可以移动到连接到它的绿色六个圆圈中的一个.计算这种迷宫中最短路径的最快方法是什么.

Answer 1

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

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

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