通过文本迷宫打印路径的算法

Question

对于我的C++作业，我基本上是在尝试搜索一个文本文件中的一段文本（该文本已流式传输到我的向量vec），从左侧第二个字符开始。这是为了一个文本迷宫，最终我的程序应该打印出通过它的路径的字符。

一个迷宫的例子可能是这样的：

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

在迷宫中，'#'代表不可行走的墙壁，你总是从左边的第二个字符开始。字母字符代表可行走的方块。出口始终在右侧。迷宫在maze.text文件中始终为15x15大小。字母字符在同一个迷宫中可能会重复出现，但不会直接相邻。

我的目标是：如果当前位置旁边的方块有字母字符，则将其添加到向量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 是我用来跟踪已访问的方格的向量。

我该如何更新它以使其实际起作用，并最终能够管理多条路径（即如果有两条路径，程序将在屏幕上打印这两条路径）？我记得有人告诉过我可能需要另一个向量/数组来跟踪我已经访问/检查过的方格，但是在这里我应该如何实现呢？

- forthewinwin

---

你需要记住自己去过哪里，这样就不会再次检查。否则你会一直向前走一步，向后退一步，没有人会像那样走得太远... - K-ballo

更新了。但是我知道我的递归调用中vec.at的位置是错误的...我应该放什么？ - forthewinwin

你也在检查你是否没有走出15x15的迷宫区域吗？ - K-ballo

我曾提供过一个答案，涉及到研究DFS和BFS，但是重新阅读了您的帖子并阅读了这些评论后，我发现您更关心的是实现问题，而不是如何找到解决方案。 - acattle

我之前看到了有关DFS和BFS的评论并阅读了维基页面，但我不确定如何将其转化为代码。 - forthewinwin

正如您可能已经看到的那样，我重新发布了我的答案，并尝试更新它以更多地讨论实现考虑事项。我还注意到，您迷宫中的字母字符不是唯一的，因此我添加了一些内容来处理这个问题。 - acattle

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”）。针对您的情况，可以制作一个简单的“Node”类，其中包括一个变量来保存字母。这样每个“e”都将有自己的实例，指针将是不同的值，让您轻松区分它们。我不知道C++的确切语法，但伪代码如下：

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

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

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

编辑：我已经作为Python开发人员度过了过去的3年，变得有点宠坏了。请看下面的代码。

s = "foo"
s == "foo"

在Python中，这个断言是正确的。"=="比较字符串的内容。我从作为Java开发人员的日子里忘记了许多语言中"=="比较字符串的指针，这就是为什么在许多像Java和C++这样的语言中，这个断言是错误的，因为字符串指向不同的内存部分。

我的观点是，由于这个断言不是真的，你可以放弃制作一个Node类，只需比较字符（使用==，而不是strcmp()！），但这段代码可能有点难以理解，必须加上注释。

总的来说，我会使用某种类型的Node类，因为它相当简单易行，并且会产生更可读的代码，而且只需要解析一次迷宫！

祝好运

- acattle