Мой 2D лабиринт повторяется бесконечно, и я получаю переполнение стека - почему?

Question

Проблема: -

Я пытаюсь решить задачу навигации 2d лабиринт в C ++, используя 2-мерный массив.Чтобы дать краткое представление о самой проблеме, я намерен перейти от узла 'S' в массиве к узлу 'G', пройдя через свободные места, обозначенные как '.'Узлы "#" являются препятствиями.Нельзя перемещаться в местах, обозначенных как препятствия.Необходимо также следить за тем, чтобы все ходы были законными (в пределах пространства конфигурации).Я обозначаю действительный ход знаком «+» после замены «.»Если вы хотите узнать больше об этой проблеме (не обязательно), пожалуйста, обратитесь по этой ссылке .

В чем проблема?

Я закодировалрекурсивный алгоритм для этой задачи, где мы получаем массив и позицию начального узла, а затем пытаемся перейти к целевому узлу с помощью рекурсии.Однако я получаю ошибку переполнения стека.Кажется, моя рекурсия никогда не прекращается.Я твердо верю, что есть какая-то проблема в моей функции play () или моей функции check ().Я не уверен, в чем на самом деле проблема.

Что я попробовал?

Я воспроизводлю свой код ниже:

void spawn(std::string (&board)[6]) {
    for (int i = 0; i <= 6; i++) {
        std::cout << board[i] << std::endl;
    }
}

bool check(size_t a, size_t b, const std::string (&board)[6]) {
    if (a < board[1].size() && a >= 0 && b < board[1].size() && b >= 0) {
        if (board[a][b] == '#' || board[a][b] == '+')
            return false;
        else if (board[a][b] == '.')
            return true;
    }
    return false;
}

void play(std::string (&board)[6], size_t a, size_t b) {
    auto status = check(a, b, board);
    if (board[a][b] == 'G' || board[a][b] == 'g') {
        spawn(board);
        return;
    }
    if (status) {
        board[a][b] = '+';
        play(board, ++a, b);
        play(board, --a, b);
        play(board, a, ++b);
        play(board, a, --b);
    }
}

int main() {
    std::string grid[6] = {{"S#####"},
                           {".....#"},
                           {"#.####"},
                           {"#.####"},
                           {"...#.G"},
                           {"##...#"}};
    play(grid, 0, 0);
    return 0;
}

Answer 1

Функция check предотвращает рекурсию, потому что она видит 'S' в сетке в начальной позиции. Изменение:

else if (board[a][b] == '.')

до

else if (board[a][b] == '.' || board[a][b] == 'S')

заставил его работать на меня.

Answer 2

Спасибо за понимание Перетта и отставной ниндзя.Я переработал функции play () и check () в свете ваших предложений, а также некоторых других идей.

Я выяснил, что основной проблемой с ошибкой сегментации было , не обеспечивающей размещение символа '\ 0' в конце массива строк grid.Я упустил это из виду, потому что считал, что массив строк функционирует не так, как массив символов (поскольку они не одного и того же вида).Теперь я понимаю, что \ 0 необходим даже для массива строк!

Я воспроизводлю переработанные функции для полноты этого поста:

void spawn(std::string board[6]) {
    for (int i = 0; i <= 6; i++) {
       std::cout << board[i] << std::endl;
    }
}

bool check(int a, int b, const std::string board[6]) {
    if (a < board[1].size() && a >= 0 && b < 
        board[1].size() && b >= 0) {
        if (board[a][b] == '#' || board[a][b] == '+') {
            return false;
        } else if (board[a][b] == '.' || 
                   board[a][b] == 'S' || 
                   board[a][b] == 'G') {
            return true;
        }
    }
    return false;
}

void play(std::string board[6], int a, int b) {
    if (board[a][b] == 'G' || board[a][b] == 'g') {
        board[0][0] = 'S';
        spawn(board);
        return;
    }
    if (board[a][b] == '.' || board[a][b] == 'S') 
        board[a][b] = '+';
    if (check(a + 1, b, board)) play(board, a + 1, b);
    if (check(a - 1, b, board)) play(board, a - 1, b);
    if (check(a, b + 1, board)) play(board, a, b + 1);
    if (check(a, b - 1, board)) play(board, a, b - 1);
    if (board[a][b] == '+') board[a][b] = '.';
}

int main() {
    std::string grid[7] = {{"S#####"},
                           {".....#"},
                           {"#.####"},
                           {"#.####"},
                           {"...#.G"},
                           {"##...#"}};
    play(grid, 0, 0);
    return 0;
}