通过文本迷宫打印到屏幕路径的算法 [英] Algorithm to print to screen path(s) through a text maze

问题描述

对于我的 C ++ 作业，我基本上试图搜索文本文件中的一大块文本（流传输到我的向量 vec ），从左边第二个顶部字符开始。它是一个文本迷宫，其中我的程序到底应该打印出的字符的路径通过它。

迷宫的示例如下：

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

其中'＃'是不知不觉的墙，你总是从左边开始第二个顶部字符。字母字符表示可步行的正方形。退出在右边。迷宫在maze.text文件中总是15x15大小。字母字符在同一个迷宫中重复，但不是直接在彼此旁边。

我想在这里做的是：如果一个正方形旁边有一个字母字符，将它添加到向量 vec ，并重复此过程，直到我到达迷宫的尽头。最终，我应该通过在屏幕上打印存在于一些迷宫中的多个路径使这更复杂。

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

  void pathcheck（）
 {
 if（isalpha（vec.at ）&&！（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））; 
} 
} 
  

$ c>是我的向量跟踪访问的广场。

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

解决方案

你在正确的轨道上。当涉及到mazes时，典型的求解方法是通过深度优先搜索（找到某个路径的最有效的解决方案）或广度优先搜索（效率较低，但是确定找到最佳路径）。由于你似乎想做一个详尽的搜索，这些选择基本上是可以互换的。我建议您阅读他们：

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，所以你的初始路径只是[ 。


2. 弹出第一个项目（在这种情况下为[S]）。


3. >从当前节点（在您的情况下，只有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 ++确切，但在伪代码：

 类Node：
方法构造函数
 myLabel = label 
 links = list（）
 
方法addLink（node）：
 links.add（node）
  

您可以读取文件中的每个字符，如果不是＃，请为该字符创建一个新的Node实例，节点。





编辑：我过去3年作为一个Python开发人员，我有点被宠坏了。查看以下代码。

  s =foo
s ==foo
  

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





我的观点是，因为这种断言不是真的，你COULD放弃一个Node类，只是比较字符（使用==，不使用strcmp（）！）但是这个代码可能有点混乱阅读，并必须记录。





总的来说，我会使用某种Node类，因为它很容易实现，并产生更可读的代码，只需要解析你的迷宫一次！





好运




For my C++ assignment, I'm basically trying to search through a chunk of text in a text file (that's streamed to my vector vec) beginning at the second top character on the left. It's for a text maze, where my program in the end is supposed to print out the characters for a path through it.

An example of a maze would be like:

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

Where '#' is an unwalkable wall and you always begin on the left at the second top character. Alphabetical characters represent walkable squares. Exit(s) are ALWAYS on the right. The maze is always a 15x15 size in a maze.text file. Alphabetical characters repeat within the same maze, but not directly beside each other.

What I'm trying to do here is: if a square next to the current one has an alphabetical character, add it to the vector vec, and repeat this process until I get to the end of the maze. Eventually I am supposed to make this more complicated by printing to the screen multiple paths that exist in some mazes.

So far I have this for the algorithm itself, which I know is wrong:

    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 is my vector keeping track of the visited squares.

How would I update this so it actually works, and eventually so I can manage more than one path (i.e. if there were 2 paths, the program would print to the screen both of them)? I recall being told that I may need another vector/array that keeps track of squares that I've already visited/checked, but then how would I implement that here exactly?

解决方案

You're on the right track. When it comes to mazes, the typical method of solving is through either a depth-first search (the most efficient solution for finding some path) or breadth-first search (less efficient, but is guarenteed to find the optimal path). Since you seem to want to do an exhaustive search, these choices are basically interchangeable. I suggest you read up on them:

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

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

Basically, you will need to parse your maze and represent it as a graph (where each non "#" is a node and each link is a walkable path). Then, you keep a list of partial paths (i.e. a list of nodes, in the order you visited them, for example, [S, b, c] is the partial path starting from S and ending at c). The main idea of DFS and BFS is that you have a list of partial paths, and one by one you remove items from the list, generate all possible partial paths leading from that partial path, then place them in the list and repeat. The main difference between DFS and BFS is that DFS implements this list as a stack (i.e. new items have greatest priority) and BFS uses a queue (i.e. new items have lowest priority).

So, for your maze using DFS it would work like this:

1. Initial node is S, so your initial path is just [S]. Push [S] into your stack ([ [S] ]).
2. Pop the first item (in this case, [S]).
3. Make a list of all possible nodes you can reach in 1 move from the current node (in your case, just b).
4. For each node from step 3, remove any nodes that are part of your current partial path. This will prevent loops. (i.e. for partial path [S, b], from b we can travel to c and to S, but S is already part of our partial path so returning is pointless)
5. If one of the nodes from step 4 is the goal node, add it to your partial path to create a completed path. Print the path.
6. For each node from step 4 that IS NOT the goal node, generate a new partial path and push it into the stack (i.e. for [S], we generate [S, b] and push it into the stack, which now should look like [ [S, b] ])
7. Repeat steps 2 through 6 until the stack is empty, meaning you have traversed every possible path from the starting node.

NOTE: in your example there are duplicate letters (for example, three "e"s). For your case, maybe make a simple "Node" class that includes a variable to hold the letter. That way each "e" will have it's own instance and the pointers will be different values letting you easily tell them apart. I don't know C++ exactly, but in pseudo code:

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

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

You could read every character in the file and if it is not "#", create a new instance of Node for that character and add all the adjacent nodes.

EDIT: I've spent the last 3 years as a Python developer and I've gotten a bit spoiled. Look at the following code.

s = "foo"
s == "foo"

In Python, that assertion is true. "==" in Python compares the string's content. What I forgot from my days as a Java developer is that in many languages "==" compares the string's pointers. That's why in many languages like Java and C++ the assertion is false because the strings point to different parts of memory.

My point is that because this assertion is not true, you COULD forgo making a Node class and just compare the characters (using ==, NOT using strcmp()!) BUT this code could be a bit confusing to read and must be documented.

Overall, I'd use some sort of Node class just because it's fairly simple to implement and results in more readable code AND only requires parsing your maze once!

Good Luck

这篇关于通过文本迷宫打印到屏幕路径的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！