使用递归在迷宫中找到最短路径？

Question

最近我一直在尝试处理一些递归迷宫代码，它返回迷宫中的最短路径。如果没有通过迷宫的路径，则代码将返回 -1。例如，对于董事会：W-S-------X-其中 S 是迷宫的起点，W 代表一堵墙，X 代表所需的目的地，而 - 代表一个可用的路径点。输出将是：2对于董事会： -SW -W- W-X输出将是 -1这一切都是通过一个带字符串和迷宫尺寸的 board 类、一个返回最短路径的检查函数和一个返回最短路径的 win 函数来实现的，如果没有路径，则返回 -1。但是，当我运行代码时，第一个示例的输出为负 1，第二个示例的输出为 1。有人可以解释我做错了什么（仅在我的新输出和所需输出之间）以及我如何解决它？编辑：谢谢peter 和mrB，我已经实施了你的建议并更新了我的代码以适应它！

Answer 1

看起来您的代码有两个问题。

首先，win()函数中的 while 循环会将您的起始位置留在板的左上角。

1. z == 0这意味着这z > 0是错误的并且不会使用 while 循环。

2. 你不增加xor y，所以 z 条件失败或者你有无限循环是好的。

其次，maxPath从不赋值。使得它0和去出界（我想第一了）所有的结果成为的结果check(x,y)，因为它是1 + 0。该-1结果都是当离开板的顶部是'W'或'X'在这种情况下check(x,y)返回0其等于maxPath

您可能还想设置check(x,y)为 int 而不是再次调用它来返回结果（更大的板可能会变得有点资源密集）。

总之

1. 更新while循环使用z == 0和增量x和y分别。

2. 设置maxPath为一个值，例如9999

3. 更改条件win()以检查check(x,y)is 的结果< maxPath（否则您可能不会得到-1结果，win()因为有可能maxPath会增加 1 或更多并!= maxPath导致 true）。

Answer 2

int right = 1 + check(r-1,c+1);

我强烈怀疑你的意思是：

int right = 1 + check(r,c+1);