C++ лабиринт решатель (найти каждое решение) переполнение стека

Question

У меня есть задание для случайного генерирования лабиринта ("странные" тоже допустимы), затем я должен найти все решения для лабиринта (решение заключается в поиске пути от первой строки или столбца до последней строки или столбца) также определите самый короткий. У меня есть этот код здесь, но когда я запускаю его, половину времени он дает хороший ответ, в другой половине он просто выходит без всплывающих окон или предупреждений об ошибках. Я предполагаю, что причиной будет переполнение стека. Кроме того, в задании сказано, что мы должны решить это в лабиринте 20х20. Если он переполняет 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)

Проблема с этими двумя вызовами заключается в том, что они вернутся к тому месту, откуда они были вызваны.

Например, если findPath вызывается с координатами 2,4, тогда первый показанный вызов вызовет findPath(3,4), который потом позвонит findPath(2,4) (который, конечно, позвонит findPAth(3,4) и тд и тд в бесконечности).