迷你程序应该打印出迷宫中所有可能的路线，其中入口/起点总是从左上角向下一个，所有可能的出口总是在右墙上 . 它从文本文件中检索迷宫 .
迷宫实际上只是一堆文字 . 迷宫由一个n×n网格组成，由作为墙壁的“＃”符号和表示可步行区域/路径的各种字母[a ... z]组成 . 信件可以重复，但永远不能并排 .
迷宫是15x15 .
大写字母S始终标记入口，位于第二高点的左侧墙壁上 . 可能的路径只能通过字母 - 你不能走＃符号 . 右墙上的任何字母代表出口 .
例如，
######
Sa#hln
#bdp##
##e#ko
#gfij#
######
是一个可能的迷宫 . 我的小程序应该在读取实际包含迷宫的文本文件后打印出所有可能的路径 .
对程序的调用将生成以下输出到屏幕：
Path 1: S,a,b,d,e,f,i,j,k,o
Path 2: S,a,b,d,p,h,l,n
2 total paths
我该怎么做呢？我不需要完整的代码答案，我只想获得一些如何解决这个问题的指导 .
到目前为止，我已经完成了除了实际算法本身之外的所有事情，它们以递归方式检查adajcent方块以查看是否可以在它们上行走，而且我不知道我是如何在多条路径上工作的 .
这是我到目前为止（我知道我的路径检查错了，但我不知道还能做什么）：
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <sstream>
#include <cstdio>
using namespace std;
ifstream file("maze.txt");
vector<char> vec(istreambuf_iterator<char>(file), (istreambuf_iterator<char>())); // Imports characters from file
vector<char> path; // Declares path as the vector storing the characters from the file
int x = 18; // Declaring x as 18 so I can use it with recursion below
char entrance = vec.at(16); // 'S', the entrance to the maze
char firstsquare = vec.at(17); // For the first walkable square next to the entrance
vector<char> visited; // Squares that we've walked over already
int main()
{
if (file) {
path.push_back(entrance); // Store 'S', the entrance character, into vector 'path'
path.push_back(firstsquare); // Store the character of the square to the right of the entrance
// into vector 'path'.
while (isalpha(vec.at(x)))
{
path.push_back(vec.at(x));
x++;
}
cout << "Path is: "; // Printing to screen the first part of our statement
// This loop to print to the screen all the contents of the vector 'path'.
for(vector<char>::const_iterator i = path.begin(); i != path.end(); ++i) //
{
std::cout << *i << ' ';
}
cout << endl;
system ("pause"); // Keeps the black box that pops up, open, so we can see results.
return 0;
}
}
谢谢！
5 回答
你需要做一些事情：
一种在内存中表示迷宫的方法 - 一种适合像迷宫这样的网格的"data structure"
访问和操纵该迷宫的方法
渲染迷宫的方法 - 也许是打印出迷宫
一种跟踪进度的方法
解决手头问题的算法
考虑从一个小得多的迷宫开始 - 也许是一个尺寸为3x3的迷宫 - 一条直线穿过 Map 的路径 . 你的程序应该能够解决这个问题 . 然后将路径更改为曲线 . 然后使 Map 更大 . 让路径更难 . 让一些“红鲱鱼”分支出路 .
较小的 Map ，复杂性越来越高，应该使调试工作变得更加容易 . （如果您不知道如何使用调试器，那么启动一个小问题将使学习调试器变得更容易 . ）
祝好运！
通常的方式（特别是对于学校作业）是递归地处理它 . 从指定的起点开始 . 从那里递归尝试每个可能的方块（上方，右侧，下方） .
这里唯一真正的“技巧”是跟踪你已经访问过哪个方块 . 一种可能性是在输入时将值保存在正方形中，然后在递归搜索其他正方形之前，将其设置为未使用的值（例如，“ . ”应该适用于您的情况） .
我首先要做的是在文件中读取并将其放入数据结构中，以便您可以实际使用它 . 如果这是作业，那么作业最有可能让你学习路径寻找算法，尝试查找Dijkstra的算法，这应该让你开始 .
一种非常高级的方法：
创建一个树，描述您可以通过迷宫的路径 . 打印出右侧的那些 .
你怎么会发现一条环绕自己的路径？ （或者你的迷宫不会有这个问题吗？）
将符号加载到数组中 . 然后递归检查每个位置：它可以向上，向下，向左，向右吗？从那里，您可以将这些布尔答案保存为0或1在一个单独的数组中，并使用它继续...根据您的副本数组是否表示您可以或不能继续在某个方向 .
另外，肯定会制作一些新方法......我通常会尝试在主要方法中包含很少...
希望有所帮助，希望我有时间更多地看待它......
-P