迷宫程序中递归算法栈溢出如何解决？

Question

我有一个解决迷宫的简单程序。但是报错：stack overflow。如何解决堆栈溢出？

在我的代码中，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("%s\r\n",szMaze[i]);
    }
}

void Maze(char szMaze[][24],int x,int y)
{
    if(szMaze[x][y]=='$')
    {
        printf("Congratulations!\r\n");
        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",
    "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);

备注

您的代码没有进行任何边界检查。因此它只有在迷宫的所有边界都有墙时才有效。有这样的要求有点“好”，但我更喜欢边界检查。

迷宫程序中递归算法栈溢出如何解决？

How to solve the recursive algorithm stack overflow in a maze program?

c

stack-overflow