这个小程序旨在打印迷宫的所有可能路径,入口/起点始终在左上角的下方一个位置,所有可能的出口始终在右侧墙壁上。 它从文本文件中检索迷宫。
实际上,迷宫只是一堆文本。 迷宫由 n x n 网格组成,其中 "#" 符号表示围墙,而各种字母 [a...z] 表示可行走区域/路径。 字母可以重复,但不能连续相邻。 这个迷宫是 15x15 的。
大写字母 S 总是表示入口,并且位于左侧墙壁的第二高位置。 可能的路径仅通过字母-您不能在 # 符号上行走。 右侧墙上的任何字母都表示出口。
例如,
实际上,迷宫只是一堆文本。 迷宫由 n x 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
如何实现这个功能?我不需要完整的代码答案,只想知道如何解决这个问题。
到目前为止,除了递归检查相邻方块是否可以行走的实际算法之外,我已经完成了所有工作,而且我不知道如何处理多条路径。
这是我目前所拥有的(我知道我的路径检查是错误的,但我不知道该怎么做):
#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;
}
}
谢谢!