我正在尝试创建一个可以通过递归解决迷宫问题的程序。我的代码基于可以在网上找到的几个步骤,特别是:
- if (x,y outside maze) 返回 false
- if (x,y is goal) 返回真
- if (x,y not open) 返回 false
- 将 x,y 标记为解决方案路径的一部分
- if (FIND-PATH(North of x,y) == true) 返回 true
- if (FIND-PATH(East of x,y) == true) 返回 true
- if (FIND-PATH(South of x,y) == true) return true
- if (FIND-PATH(West of x,y) == true) 返回 true
- 取消将 x,y 标记为解决方案路径的一部分
- 返回错误
我已经看到至少两个关于此算法的其他问题,但我很确定这些问题并不完全相同。
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”(在北检查之后发现)没有。我不确定我的递归逻辑或我的递归实现是否存在某种形式的问题,所以我希望得到一些澄清。
提前致谢!
最佳答案
您第一次检查 bool path(...)
发现 x<0 因为 x==-1,所以该函数返回 false
并退出,而 main程序从对 path
的调用中得到一个 false
结果,打印他必须打印的内容并退出。
您应该从有效位置开始检查。
关于c++ - 使用递归解决 C++ 中的迷宫问题?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16111398/