c++ - 通过文本迷宫打印到屏幕路径的算法

Question

对于我的 C++ 作业，我基本上是尝试从第二个开始搜索文本文件中的一段文本(流式传输到我的 vector vec)左边的顶部字符。它用于文本迷宫，我的程序最后应该打印出通过它的路径的字符。

迷宫的例子如下:

###############
Sbcde####efebyj
####hijk#m#####
#######lmi#####
###############
###############
###############
###############
###############
###############
###############
###############
###############
###############
###############

其中“#”是一堵不可行走的墙，您始终从左侧第二个顶部字符开始。字母字符代表可步行的方 block 。导出总是在右边。 maze.text 文件中的迷宫大小始终为 15x15。字母字符在同一个迷宫中重复出现，但并不直接相邻。

我想在这里做的是:如果当前方 block 旁边的方 block 有一个字母字符，将它添加到 vector vec，并重复这个过程，直到我到达终点的迷宫。最终我应该通过在屏幕上打印存在于某些迷宫中的多条路径来使这变得更加复杂。

到目前为止，我对算法本身有这个，我知道这是错误的:

    void pathcheck()
{
    if (isalpha(vec.at(x)) && !(find(visited.begin(), visited.end(), (vec.at(x))) != visited.end()) )
    {
        path.push_back(vec.at(x));
        visited.push_back(vec.at(x));
        pathcheck(vec.at(x++));
        pathcheck(vec.at(x--));
        pathcheck(vec.at(x + 16));
        pathcheck(vec.at(x - 16));
    }
}

visited 是我跟踪访问过的方 block 的 vector 。

我将如何更新它，使其真正起作用，并最终让我可以管理多个路径(即，如果有 2 条路径，程序会将它们都打印到屏幕上)？我记得有人告诉我，我可能需要另一个 vector/数组来跟踪我已经访问/检查过的方 block ，但我该如何在这里准确地实现它？

Answer 1

您走在正确的轨道上。当涉及到迷宫时，典型的解决方法是通过深度优先搜索(找到某条路径的最有效解决方案)或广度优先搜索(效率较低，但保证找到最佳路径)。由于您似乎想要进行详尽的搜索，因此这些选择基本上可以互换。我建议您仔细阅读它们:

http://en.wikipedia.org/wiki/Depth-first_search

http://en.wikipedia.org/wiki/Breadth-first_search

基本上，您需要解析您的迷宫并将其表示为图形(其中每个非“#”都是一个节点，每个链接都是一条可步行的路径)。然后，您保留一个部分路径列表(即节点列表，按照您访问它们的顺序，例如 [S, b, c] 是从 S 开始到 c 结束的部分路径)。 DFS 和 BFS 的主要思想是你有一个部分路径列表，你从列表中逐一删除项目，生成从该部分路径引出的所有可能的部分路径，然后将它们放入列表并重复。 DFS 和 BFS 之间的主要区别在于 DFS 将此列表实现为堆栈(即新项目具有最高优先级)，而 BFS 使用队列(即新项目具有最低优先级)。

因此，对于使用 DFS 的迷宫，它会像这样工作:

1. 初始节点是S，所以你的初始路径就是[S]。将 [S] 插入您的堆栈 ([ [S] ])。
2. 弹出第一个项目(在本例中为 [S])。
3. 列出所有可能的节点，您可以从当前节点移动 1 次(在您的情况下，只是 b)。
4. 对于第 3 步中的每个节点，删除属于当前部分路径的所有节点。这将防止循环。 (即对于部分路径 [S, b]，我们可以从 b 到 c 再到 S，但是 S 已经是我们部分路径的一部分，所以返回是没有意义的)
5. 如果第 4 步中的节点之一是目标节点，请将其添加到您的部分路径以创建完整路径。打印路径。
6. 对于第 4 步中不是目标节点的每个节点，生成一个新的部分路径并将其压入堆栈(即对于 [S]，我们生成 [S, b] 并将其压入堆栈，现在应该看起来像 [ [S, b] ])
7. 重复步骤 2 到 6，直到堆栈为空，这意味着您已经遍历了从起始节点开始的所有可能路径。

注意:在您的示例中有重复的字母(例如，三个“e”)。对于您的情况，也许可以创建一个简单的“节点”类，其中包含一个用于保存字母的变量。这样每个“e”都会有它自己的实例，指针将是不同的值，让您轻松区分它们。我不完全了解 C++，但在伪代码中:

class Node:
    method Constructor(label):
        myLabel = label
        links = list()

    method addLink(node):
        links.add(node)

您可以读取文件中的每个字符，如果它不是“#”，则为该字符创建一个新的 Node 实例并添加所有相邻节点。

编辑:在过去的 3 年里，我一直是一名 Python 开发人员，我有点被宠坏了。看下面的代码。

s = "foo"
s == "foo"

在 Python 中，该断言是正确的。 Python 中的“==”比较字符串的内容。作为一名 Java 开发人员，我忘记了在许多语言中“==”比较字符串的指针。这就是为什么在 Java 和 C++ 等许多语言中断言为假的原因，因为字符串指向内存的不同部分。

我的观点是因为这个断言是不正确的，你可以放弃创建一个 Node 类而只比较字符(使用 ==，而不是使用 strcmp()!)但是这段代码读起来可能有点困惑，必须被记录下来。

总的来说，我会使用某种 Node 类，因为它实现起来相当简单，代码可读性更强，而且只需要解析一次迷宫!

祝你好运