c++ - 追踪迷宫以从源头到达目标

Question

我正在尝试实现一个问题的解决方案，其中我需要在迷宫中从源头到目标递归地找到一条路径。

假设这是迷宫:
小号 X X X X X
. . . . . X
X 。 X X X X
X 。 X X X X
. . . X 。 G
××。 . . X
哪里

X- 阻塞路径

.- 打开路径

S-开始

G -目标

我已经编写了以下代码来实现该解决方案，但它给了我一个段错误。如果有人可以建议我哪里做错了，我会很高兴。

我的解决方案是

#include<iostream>
using namespace std;
void printGrid(char grid[6][6])
{
    for(int i=0;i<6;i++)
    {
        for(int j=0;j<6;j++)
        {
            cout<<grid[i][j]<<" ";
        }
        cout<<"\n";
    }
}

bool isValidPoint(char grid[6][6],int x,int y)
{   
    if(x<0 || x>5 || y<0 || y>5)
    {
        return false;
    }
    if(grid[x][y]=='X')
    {
        return false;
    }
    return true;
}

bool traceMaze(char grid[6][6],int x,int y)
{
    if(!isValidPoint(grid,x,y))
    {
        return false;
    }
    if(grid[x][y]=='G')
    {
        return true;
    }

    grid[x][y] = '+';

    if(traceMaze(grid,x-1,y)){return true;}
    if(traceMaze(grid,x,y+1)){return true;}
    if(traceMaze(grid,x+1,y)){return true;}
    if(traceMaze(grid,x,y-1)){return true;}

    grid[x][y] = '.';

    return false;

}


int main()
{
    char grid[6][6] = {{'S','X','X','X','X','X'},{'.','.','.','.','.','X'},{'X','.','X','X','X','X'},{'X','.','X','X','X','X'},{'.','.','.','X','.','G'},{'X','X','.','.','.','X'}};
    cout<<"Initial grid is as follows :\n";
    printGrid(grid);
    cout<<"\nStarting at : (0,0)\nTracing the path to the Goal\n";
    cout<<traceMaze(grid,0,0)<<"\n";
    cout<<"\nFinal grid is as follows :\n";
    printGrid(grid);
    return 0;
}

PS:我假设迷宫的大小是 6X6...

Correct Solution : 

我没有对“+”进行任何检查以查看最终跟踪路径。

所以现在我在那里应用了检查，isValidPoint 函数转换为:

bool isValidPoint(char grid[6][6],int x,int y)
{   
    if(x<0 || x>5 || y<0 || y>5)
    {
        return false;
    }
    if(grid[x][y]=='X' || grid[x][y]=='+')
    {
        return false;
    }
    return true;
}

谢谢大家的帮助:)

我去年接受了这个问题的全职面试。

Answer 1

没有什么可以阻止您的 traceMaze 函数无限递归。也就是说，它将从一个网格点移动到下一个网格点，然后再回到原来的位置。

最简单的解决方法是不要将其中带有“+”的点视为进入的有效点(因为您已经在这条路径中到达那里)。