使用递归解决C中的迷宫？

Question

我正在尝试创建一个可以通过递归解决迷宫的程序。我的代码基于可以在网上找到的几个步骤，特别是：

1. if（x， y在迷宫外）返回false
2. if（x， y是目标）返回true
3. if（x， y not open）返回false
4. 将x， y标记为解路径的一部分
5. if（FIND-PATH（x， y的北方）==true）返回true
6. if（FIND-PATH（East of x， y）==true）返回true
7. if（FIND-PATH（x， y以南）==true）返回true
8. if（FIND-PATH（West of x， y）==true）返回true
9. 将x， y标记为解路径的一部分
10. 返回false

我已经看到了这个算法的另外两个问题，但我很确定这些问题并不完全相同。

bool path (string maze[], int x, int y){
    values val;
    bool check;
    //for (int k=0; k<val.xDim; k++) cout<<maze[k]<<endl;
    cout<<x<<":"<<y<<endl;
    if (x>val.xDim || y>val.yDim || x<0 || y<0) {cout<<"end\n"; return false;  }
    if (maze[x][y]=='x') return true;                           //If exit is reached
    if (maze[x][y]=='%' || maze[x][y]=='+') return false;       //If space is filled
    maze[x][y]='+';
    if (path(maze, x-1, y)==true) return true;
    cout<<"endtwo\n";
    if (check=path(maze, x, y+1)==true) return true;
    if (path(maze, x+1, y)==true) return true;
    if (path(maze, x, y-1)==true) return true;
    maze[x][y]='.';
    return false;
}

int main(){
    if (path(maze, val.startX-1, val.startY)==true) {
        for (int k=0; k<val.xDim; k++) cout<<maze[k]<<endl;
    } else cout<<"No solution found.\n";
}

样本迷宫为（其中e为入口，x为出口）：

%e%%%%%%%%%
%...%.%...%
%.%.%.%.%%%
%.%.......%
%.%%%%.%%.%
%.%.....%.%
%%%%%%%%%x%

输出：

-1:1
end
No solution found.

据我所知，路径方法应该从检查入口正上方的空间开始，该空间位于迷宫之外（返回false）。接下来，它应该检查east（以此类推）。但是，当我运行它时，函数返回false，并且无法继续执行以下if语句。这一点可以通过打印“end”而不是“endtwo”（在north check之后找到）这一事实来证明。我不确定我的递归逻辑或我的递归实现是否存在某种形式的问题，所以我希望对此有一些澄清。

提前谢谢！

Answer 1

你从一个无效的位置开始，所以不要用这个if（path（maze，val.startX-1，val.startY）==true）{，试试这个if（path（maze，val.startX，val.startY）==true）{。实际的递归部分对我来说似乎没问题，只要你不介意用'替换迷宫中的'e'。。

Answer 2

您的第一次签入bool路径（…） 查找x

你应该从一个有效的位置开始你的支票。