3

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

  1. 如果 (x,y 在迷宫外) 返回 false
  2. 如果 (x,y 是目标) 返回 true
  3. 如果 (x,y 未打开) 返回 false
  4. 将 x,y 标记为解决方案路径的一部分
  5. if (FIND-PATH(x,y 以北) == true) 返回 true
  6. if (FIND-PATH(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. 返回假

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

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”（在北检查后找到）这一事实来证明。我不确定我的递归逻辑或递归实现是否存在某种形式的问题，所以我希望对此有所澄清。

提前致谢！

4

2 回答 2

4

您的第一次签入bool path(...)发现 x<0，因为 x==-1，因此函数返回false并退出，主程序false从调用中获取结果path，打印他必须执行的内容并退出。

你应该从一个有效的位置开始你的检查。

于 2013-04-19T18:52:41.267 回答
0

你是从一个无效的位置开始的，所以不要这样if (path(maze, val.startX-1, val.startY)==true) {，试试这个if (path(maze, val.startX, val.startY)==true) {。实际的递归部分对我来说似乎没问题，前提是您不介意'e'用'.'.

于 2013-04-19T19:11:02.690 回答