我的 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;
}
问题:-
我正在尝试使用二维数组解决 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;
}