C++“迷宫”任务

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

那我该怎么做呢？我不需要一个完整的代码答案，我只需要一些关于如何处理这个问题的指导。

到目前为止，我已经做了所有的事情，除了实际的算法本身，递归地检查正方形，看看你是否可以在它们上行走，我不知道如何在多条路径上工作。

这就是我到目前为止所拥有的(我知道我的路径检查是错误的，但我不知道还能做什么)：

    #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. 跟踪进度的方法

<代码>H19解决手头问题的算法<代码>H210<代码>G211

考虑从一个小得多的迷宫开始--可能是3x3大小的迷宫--有一条径直穿过地图的路径。你的程序应该能够解决这个问题。然后改变路径，使其稍微弯曲一点。然后把地图放大。让这条路更难走。在小路上插上一些“转移注意力的”树枝。

一个更小的map，增加了复杂性，应该会使调试工作变得容易得多。(如果您不知道如何使用调试器，那么从一个小问题开始将使学习调试器变得更容易。)

祝好运!

Answer 2

通常的方法(特别是对于学校作业)是递归处理它。从指定的起点开始。从那里递归地尝试每个可能的方块(上面，右边，下面)。

唯一真正的“诀窍”是跟踪你已经访问过的广场。一种可能是在输入时将值保存在正方形中，然后在递归搜索其他正方形之前，将其设置为其他情况下不使用的值(例如，‘’)。应该适用于您的情况)。

Answer 3

当然，我首先要做的是读取文件，并将其放入数据结构中，这样您就可以实际使用它了。如果这是家庭作业，那么作业最有可能是让你学习路径查找算法，尝试查找Dijkstra的算法，这应该会让你开始。