C++ "Maze"赋值

Question

这个小程序应该打印出迷宫中所有可能的路线，入口/起点总是从左上角向下一个，所有可能的导出总是在右墙上。它从文本文件中检索迷宫。

迷宫其实就是一堆文字。迷宫由 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

我会怎么做呢？我不需要完整的代码答案，我只需要有关如何解决此问题的一些指导。

到目前为止，除了递归检查相邻方 block 以查看您是否可以在其上行走的实际算法本身之外，我已经完成了所有工作，而且我不知道如何在多条路径上工作。

这是我目前所做的(我知道我的路径检查是错误的，但我不知道还能做什么):

    #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;
        }
}

谢谢!

Answer 1

您需要做一些事情才能开始:

1. 一种在内存中表示迷宫的方法——一种适用于像迷宫这样的网格的“数据结构”
2. 进入和操纵迷宫的方法
3. 一种绘制迷宫的方法——可能是打印出一个迷宫
4. 一种跟踪进度的方法
5. 解决手头问题的算法

考虑从一个小得多的迷宫开始——也许是一个 3x3 大小的迷宫——有一条直接穿过 map 的路径。你的程序应该能够解决这个问题。然后将路径更改为曲线一点。然后把 map 放大。让道路更艰难。在路径上放一些“红鲱鱼”分支。

map 越小，越复杂，调试起来应该会容易得多。 (如果您不知道如何使用调试器，从一个小问题入手将使学习调试器更容易。)

祝你好运!