c++ - 使用递归解决 C++ 中的迷宫问题？

Question

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

1. if (x,y outside maze) 返回 false
2. if (x,y is goal) 返回真
3. if (x,y not open) 返回 false
4. 将 x,y 标记为解决方案路径的一部分
5. if (FIND-PATH(North of x,y) == true) 返回 true
6. if (FIND-PATH(East of x,y) == true) 返回 true
7. if (FIND-PATH(South of x,y) == true) return true
8. if (FIND-PATH(West of x,y) == true) 返回 true
9. 取消将 x,y 标记为解决方案路径的一部分
10. 返回错误

我已经看到至少两个关于此算法的其他问题，但我很确定这些问题并不完全相同。

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)。在此之后，它应该检查东方(等等)。但是，当我运行它时，该函数返回 false 并且无法继续执行以下 if 语句。事实表明，“end”被打印出来，而“endtwo”(在北检查之后发现)没有。我不确定我的递归逻辑或我的递归实现是否存在某种形式的问题，所以我希望得到一些澄清。

提前致谢!

Answer 1

您第一次检查 bool path(...) 发现 x<0 因为 x==-1，所以该函数返回 false 并退出，而 main程序从对 path 的调用中得到一个 false 结果，打印他必须打印的内容并退出。

您应该从有效位置开始检查。