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

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 是我的矢量跟踪访问过的广场.

我如何更新它,以便它实际工作,最终我可以管理多个路径(即如果有2个路径,程序将打印到屏幕上的两个路径)？我记得被告知我可能需要另一个矢量/数组来跟踪我已经访问/检查过的方块,但是我如何在这里实现呢？

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 实例并添加所有相邻节点。

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

s = "foo"
s == "foo"

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

我的观点是，因为这个断言是不正确的，所以您可以放弃创建 Node 类，而只比较字符（使用 ==，而不是使用 strcmp()！），但是这段代码可能有点难以阅读，必须记录下来。

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

祝你好运