c++迷宫解算器(查找所有解决方案)堆栈溢出

Question

我有一个任务要随机生成一个迷宫（"奇怪"的也有效），然后我必须找到迷宫的所有解决方案（一个从第一行或列到最后一行或列的解决方案），并确定最短的一个。我这里有这个代码，但当我运行它时，一半时间它给出了一个好的答案，另一半时间它只是退出，没有任何错误弹出或警告。我想原因可能是堆栈溢出。此外，在作业中，它说我们必须在20x20的迷宫中解决这个问题。如果它在5x5上溢出，你能想象一个20x20吗？不管怎样，任何帮助都将不胜感激。请忽略这些评论，匈牙利语评论实际上是任务的一部分。

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
struct vector2d {
    int column, row;
};
const int N = 5;        // sorok száma
const int M = 5;        // oszlopok száma
bool ut[N][M];
int count = 0;
int currentLength = 0, minLength = 99999;
void initMaze();         // generál egy labirintust
void printMaze();        // kiiratja a labirintust
int exits();             // kijáratok számát adja vissza
int entrances();         // bejáratok számát adja vissza
bool findPath(int, int); // útkereső eljárás
int main() {
    initMaze();
    printMaze();
    if (exits() > 0 && entrances() > 0) {
        // bactrack
        for (int i = 0; i < M; i++) // vegigjarjuk az elso sor osszes "utjat" es megkeressuk az onnan indulo megoldasokat
            if (ut[0][i])
                if (findPath(0, i)) {
                    count++;
                    if (currentLength < minLength)
                        minLength = currentLength;
                    currentLength = 0;
                }
        for (int i = 1; i < M; i++)
            if (ut[i][0])
                if (findPath(i, 0)) {
                    count++;
                    if (currentLength < minLength)
                        minLength = currentLength;
                    currentLength = 0;
                }
    } else {
        cout << "Maze has no entrances or exits" << endl;
    }
    if (count > 0) {
        cout << count << " solutions for the labyrinth, shortest one is " << minLength << " steps long" << endl;
    } else {
        cout << "Labyrinth has no solution" << endl;
    }
    system("pause");
    return 0;
}
int exits() {
    int count = 0;
    for (int i = 1; i < M - 1; i++)
        if (ut[N - 1][i])
            count++;
    for (int i = 1; i < N - 1; i++)
        if (ut[i][M - 1])
            count++;
    return count;
}
int entrances() {
    int count = 0;
    for (int i = 1; i < M - 1; i++)
        if (ut[0][i])
            count++;
    for (int i = 1; i < N - 1; i++)
        if (ut[i][0])
            count++;
    return count;
}
void initMaze() {
    srand(time(NULL));
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++) {
            if (rand() % 3 == 0) // 3-ból egyszer legyen fal
                ut[i][j] = false;
            else
                ut[i][j] = true;
        }
}
void printMaze() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (ut[i][j])
                cout << " - ";
            else
                cout << " | ";
        }
        cout << endl;
    }
}
bool findPath(int row, int column) {
    if (column < 0 || column > N - 1 || row < 0 || row > M - 1) return false;
    if ((column == M - 1 || row == N - 1) && ut[row][column])   return true;
    if (!ut[row][column])                                       return false;
    currentLength++;
    if (findPath(column + 1, row))                              return true;
    if (findPath(column, row + 1))                              return true;
    if (findPath(column - 1, row))                              return true;
    if (findPath(column, row - 1))                              return true;
    currentLength--;
    return false;
}

Answer 1

您有递归调用

findPath(column + 1, row)

这个函数将在一段时间后调用这个递归

findPath(column - 1, row)

这两个呼叫的问题是，它将返回到呼叫的位置。

例如，如果用坐标2，4调用findPath，则所示的第一个调用将调用findPath(3,4)，然后调用findPath(2,4)（当然，在无穷大中调用findPAth(3,4)等等）。