java - 迷宫求解器的递归

Question

该项目是使用递归和树在 Java 中编写迷宫求解器(我使用自己的链表，不确定它是否是树，但我不介意)。

讲师从不解释任何内容，所以我所有的知识都是在网上获得的。我的递归方法遇到问题，我不知道该怎么做，因为我找不到与我的项目相关的示例

在我的链接列表中，我有指向右侧、左侧、底部和顶部节点的链接。例如，如果您的右侧有一堵墙，则该链接将为空。我在链接列表 wallRight、wallLeft、wallBottom 和 wallTop 中也有 boolean 值，看看是否有例如右边有一堵墙。因此，如果右侧有一堵墙，“Right”链接将为 null，并且 wallRight 将为 true。

我还使用图像标签，因此如果我落在某个位置，就会显示图像。我创建了一个方法，如果我位于位置 1，则会显示标签 1，因此在递归方法中，我使用 int pos 来了解要显示哪个标签。

现在我的递归方法遇到了麻烦。我已经尝试过两种方法，但都不起作用。这是它们两个:

public boolean move(Maze rigting,int pos) // Righting = direction
{
   if(rigting.goal == true)
       return true; //BASE CASE - tests if it is on the goal node

   else if(rigting.wallR != true) //checks if there is a wall on the right
   {
       pos += 1;
       move(rigting.right, pos); //moves right

       showLabel(pos);
       return true;
   }

   else if(rigting.wallD != true) //checks if there is a wall below
   {
       pos += 10;
       move(rigting.down, pos); //moves down

       showLabel(pos);
       return true;
   }

   else if(rigting.wallL != true) //checks if there is a wall on the left
   {
       pos -= 1;
       move(rigting.left, pos); //moves left

       showLabel(pos);
       return true;
   }

   else if(rigting.wallU != true) //checks if there is a wall above
   {
       pos -= 10;
       move(rigting.up, pos); //moves up

       showLabel(pos);
       return true;
   }

   return false; //I know this return is incorrect, but it won't run without one
 }

<小时/>

public boolean move(Maze rigting,int pos) //Righting = direction
{
    if(rigting.goal == true)
        return true;

    return (rigting.wallR != true) ? move(rigting.right, pos += 1) : false ||
    (rigting.wallD != true) ? move(rigting.down, pos += 10) : false ||
    (rigting.wallL != true) ? move(rigting.left, pos -= 1) : false ||
    (rigting.wallU != true) ? move(rigting.up, pos -= 10) : false;
}

这两个都会给出 stackoverflow 异常...
我认为我的错误是，如果右侧有墙，则链接右侧为null。如果我能以某种方式使所有链接都不为 null，那么我就不需要 boolean 值 wallRight 等，但我不知道如何实现它。

如果您能给我指明正确的方向，我将不胜感激!我只需要在 10 月 10 日交项目，所以如果我做得完全错误，我不介意重新开始!

Answer 1

由于这是你的作业，我不会在这里给你解决方案，而是给你一些提示。

1. 您的第一个解决方案不会考虑后续调用 move() 的结果，因此只有在您(意外地)达到目标时，递归才会结束。
2. 在第二个解决方案中，您考虑了结果，但没有为循环移动的情况做好准备。您需要标记您已经访问过的节点并在那里中断(返回值 false)。

对于递归，最好从中断条件开始(就像您所做的那样)，然后实现一个简单的情况(例如总是向右走)。管理简单的案例后，您可以添加其他(分支)