首页 文章

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

提问于
浏览 次
2

我正在尝试创建一个可以通过递归解决迷宫的程序 . 我的代码基于可以在网上找到的几个步骤，具体来说：

  • if（x，y外迷宫）返回false

  • if（x，y是goal）返回true

  • if（x，y not open）返回false

  • 标记x，y作为解决方案路径的一部分

  • if（FIND-PATH（x，y之前）== true）返回true

  • if（FIND-PATH（东经x，y）== true）返回true

  • if（FIND-PATH（x，y之后）== true）返回true

  • if（FIND-PATH（西x，y）== true）返回true

  • unmark x，y作为解决方案路径的一部分

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

提前致谢！

c++ recursion maze

2 回答

  • 0

    你在 bool path(...) 中的第一次检查发现x <0，因为x == - 1，所以函数返回 false 并退出，主程序从 path 调用获得 false 结果，打印出他已经输出和退出的内容 .

    你应该用有效的职位开始你的支票 .

    回复于
  • 4

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

    回复于

相关问题