迷你程序应该打印出迷宫中所有可能的路线,其中入口/出发点总是从左上角向下,所有可能的出口始终在右侧壁。它从文本文件中检索迷宫。C++“迷宫”作业
迷宫实际上只是一堆文本。 迷宫由一个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方块以查看是否可以在它们上行走,并且我不知道如何在多个路径上工作,我已经做了所有事情。
这是我迄今为止(我知道我的pathcheck是错的,但我不知道我还能做什么):
#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;
}
}
谢谢!
你有什么试过的?您是否陷入了解决方案的某些方面?你是否已经完成了基础知识,比如将文件中的迷宫读入程序中的数据结构中? –
是否允许使用递归函数? –
我会使用递归和保存当前状态的列表,每次递归都会为下一步做4次递归调用。在每次递归时检查当前位置是否已被访问,以及是否为结束块。 – bdares