我的 2D 迷宫解算器无限递归并且出现堆栈溢出 - 为什么?

My 2D maze solver recurses infinitely and I get a stack overflow - why?

问题:-

我正在尝试使用二维数组解决 C++ 中的二维迷宫导航问题。为了简要说明问题本身,我打算通过遍历由“.”表示的空闲 space 来从数组中的节点 'S' 导航到节点 'G'。节点“#”是障碍物。不允许在表示为障碍物的 space 上移动。还必须注意使所有移动都成为合法移动(在配置 space 内)。在替换“.”之后,我用“+”表示有效的移动。如果您想了解更多关于此问题的信息(不是必需的),请参考此 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;
}

check 函数阻止递归,因为它在起始位置看到网格中的 'S'。变化:

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

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

它对我有用。

感谢 Perette 和 Retired Ninja 的见解。我根据您的建议以及我自己的一些想法重构了 play() 和 check() 函数。

我发现分段错误的主要问题没有为'\0'字符提供住宿字符串数组的结尾 grid。我忽略了它,因为我认为字符串数组以不同于字符数组的方式运行(因为它们不是同一物种)。现在我意识到 '\0' 即使对于字符串数组也是必要的!

为了完整 post,我正在重现重构函数:

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;
}