我的2D迷宫求解器无限地递归，我得到了堆栈溢出 - 为什么？

Question

问题 ：-

我试图用二维数组解决C ++中的2d迷宫导航问题。为了简要介绍问题本身，我打算通过遍历“。”表示的自由空间从数组中的节点“S”导航到节点“G”。节点'＃'是障碍物。一个人不允许在被称为障碍物的空间上移动。还必须注意将所有动作视为合法移动（在配置空间内）。在替换''后，我用'+'表示有效的移动。如果您想更多地了解这个问题（没有必要），请参考这个link。

有什么问题？

我为这个问题编写了一个递归算法，我们接收一个数组和一个起始节点位置，然后尝试使用递归导航到目标节点。但是，我收到堆栈溢出错误。看起来我的递归永远不会停止。我坚信我的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

感谢Perette和Retired Ninja的见解。我根据你的建议重构了play（）和check（）函数，还有我自己的一些想法。

我发现分段错误错误的主要问题是没有为字符串grid数组末尾的'\ 0'字符提供调整。我忽略了它，因为我认为字符串数组的运行方式与字符数组不同（因为它们不是同一种类）。现在我意识到'\ 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;
}