我正在尝试使用回溯编写迷宫求解器。它应该看看是否有可能从起点 S 到终点 E 解决给定的难题。伪代码可以在这个 link 中看到。这里。我的实现如下所示:
const int N = 8; // global var
bool exploreMaze(char maze[][N], int x, int y)
{
if(y >= 8 || y < 0 || x >= 7 || x < 0) // null char at end of each 1d array
return false;
if(maze[x][y] == '*')
return false;
if(maze[x][y] == 'E')
return true;
maze[x][y] = '*'; // set grid to '*' as to not loop infinitely
if(exploreMaze(maze, x + 1, y))
{
cout << "up" << ", ";
return true;
}
if(exploreMaze(maze, x - 1, y))
{
cout << "down" << ", ";
return true;
}
if(exploreMaze(maze, x, y - 1))
{
cout << "left" << ", ";
return true;
}
if(exploreMaze(maze, x, y + 1))
{
cout << "right" << ", ";
return true;
}
return false;
}
bool isMazeSolvable(char maze[][N])
{
int startX = -1, startY = -1;
for(int i = 0; i < N; i++)
{
for(int j = 0; j < N; j++)
{
if(maze[i][j] == 'S')
startX = i;
startY = j;
}
}
if(startX == -1)
return false;
return exploreMaze(maze, startX, startY);
}
int main()
{
char maze[N][N] = {"*******", " S ", "*******", " E ", "*******",
"*******", "*******", "*******"};
cout << isMazeSolvable(maze);
return 0;
}
我在 main 中测试的数组肯定没有解决方案,但不知何故我得到 1(true) 作为输出。有什么想法吗?
最佳答案
您的迷宫“*”仅在 Y 方向上初始化了 7 个字符,但您的迷宫漫游器检查了 8 个字符。这允许它绕着墙的尽头走动。
我添加了一个快速迷宫打印功能并将 exploreMaze
更改为放置 '.'它走的地方。提供以下输出:
Initial maze:
*******
S
*******
E
*******
*******
*******
*******
left, left, left, left, left, up, up, right, right, right, right, right, right,
1
After explore:
*******
.......
*******.
E.....
*******
*******
*******
*******
解决方案:要么将初始化器更改为使用 8 个字符的墙,要么将 exploreMaze
函数更改为仅在 Y 方向上看 7 个字符。
另请注意:您没有执行迷宫求解器的“回溯”部分,因为您标记了您去过的地方,但没有在退出递归的途中清除您的路径。添加
maze[x][y] = ' '; // Clear the grid so we can try this spot again in another recursion
到你的 exploreMaze
函数的末尾
关于c++ - 回溯迷宫,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31737216/