如何从迷宫创建图形

Question

我想实现本周在课堂上学到的一些图和生成树的东西，所以我创建了一个基于Prim算法的迷宫生成算法。现在，我正在尝试创建一种算法来有效地解决迷宫。到目前为止，我已经做了一个洪水填充，最终解决了迷宫，但效率非常低。我现在正试图找到一种方法将迷宫转换为图形，以便使用 Dijkstra 的算法或 DFS，但我被难住了。迷宫存储在二进制数组中，其中 1 是一堵墙，0 是开放空间。迷宫总是从第一行中唯一的 0 开始，到最后一行中唯一的零结束。迷宫的存储如下图所示。

static int maze2[][] = {{1, 1, 1, 1, 1, 0, 1, 1, 1, 1},
                        {1, 1, 1, 0, 0, 0, 0, 0, 0, 1},
                        {1, 0, 0, 0, 1, 0, 1, 0, 0, 1},
                        {1, 0, 0, 1, 1, 0, 1, 1, 0, 1},
                        {1, 1, 0, 0, 1, 0, 1, 1, 0, 1},
                        {1, 0, 0, 1, 1, 0, 1, 0, 0, 1},
                        {1, 1, 0, 0, 1, 0, 1, 0, 1, 1},
                        {1, 0, 0, 1, 1, 0, 1, 0, 0, 1},
                        {1, 1, 0, 0, 1, 0, 1, 0, 1, 1},
                        {1, 1, 1, 1, 1, 0, 1, 1, 1, 1}};

Answer 1

您不会将迷宫转换为图形。 你只是把它想象成一个图表。

当你编写算法(BFS、DFS等(时，你只需要：

• 一种标识节点的方法 - (行，列(对工作正常，或者您可以使用单个整数行*宽度+列。
• 一种查找相邻节点的方法 - 只需检查矩阵中的相邻单元格。