c-如何解决迷宫程序中递归算法堆栈溢出的问题

Question

我有一个简单的程序来解决迷宫。但报告了一个错误：堆栈溢出。如何解决堆栈溢出问题？

在我的代码中，1代表墙，0代表可以走的路径，$代表终点。(1,2(是起点。

这是我的代码：

#include<stdio.h>
#include<windows.h>
void ShowMaze(char szMaze[][24],int nCount)
{

for(int i=0;i<nCount;i++)
{
printf("%srn",szMaze[i]);
}
}
void Maze(char szMaze[][24],int x,int y)
{
if(szMaze[x][y]=='$')
{
printf("Congratulations!rn");
system("pause");
exit(0);
}
if (szMaze[x+1][y]=='$'||szMaze[x+1][y]=='0')
{
Maze(szMaze,x+1,y);
}
if (szMaze[x][y+1]=='$'||szMaze[x][y+1]=='0')
{
Maze(szMaze,x,y+1);
}
if (szMaze[x-1][y]=='$'||szMaze[x-1][y]=='0')
{
Maze(szMaze,x-1,y);
}
if (szMaze[x][y-1]=='$'||szMaze[x][y-1]=='0')
{
Maze(szMaze,x,y-1);
}

return;
}
int main()
{
char szMaze[][24]={
"11111111111111111111111",
"10111111111111111111111",
"10000000001111111111011",
"11111111011111100001011",
"11111111011111101111011",
"11111111000000000001$11",
"11111111011111101111011",
"11111111011111100000001",
"11111111111111111111111"
};
int nRow=sizeof(szMaze)/sizeof(szMaze[0]);
ShowMaze(szMaze,nRow);
Maze(szMaze,1,2);

system("pause");
return 0

Answer 1

为了避免无休止的循环，您需要标记已经访问过的位置。

类似于：

szMaze[x][y]='2'; // mark position as visited
if (szMaze[x+1][y]=='$'||szMaze[x+1][y]=='0')
{
Maze(szMaze,x+1,y);
}
if (szMaze[x][y+1]=='$'||szMaze[x][y+1]=='0')
{
Maze(szMaze,x,y+1);
}
if (szMaze[x-1][y]=='$'||szMaze[x-1][y]=='0')
{
Maze(szMaze,x-1,y);
}
if (szMaze[x][y-1]=='$'||szMaze[x][y-1]=='0')
{
Maze(szMaze,x,y-1);
}
szMaze[x][y]='0'; // release position

不要从墙上开始！启动方式：

Maze(szMaze,1,2); ---->   Maze(szMaze,1,1);

注意

您的代码不进行任何边界检查。因此，只有当迷宫的所有边界都有墙时，它才会起作用。有这样的要求有点像"；好的"；但我更喜欢边界检查。