0

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

讲师从不解释任何东西，所以我把所有的知识都放在网上。我的递归方法有问题，我不确定该怎么做，因为我找不到与我的项目相关的示例

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

我还使用图像标签，所以如果我降落在一个地方，就会显示图像。我做了一个方法，如果我在位置 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异常......
我认为我的错误是，如果右边有一堵墙，那么链接 Right 是null. 如果我能以某种方式使它没有任何链接null，那么我就不需要布尔值wallRight等，但我不知道如何实现它。

如果你能把我送到正确的方向，我将不胜感激！我只需要在 10 月 10 日提交项目，所以如果我做错了，我不介意重新开始！

4

1 回答 1

1

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

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

对于递归，最好从中断条件开始（就像您所做的那样），然后实现一个简单的案例（例如，总是正确）。管理简单案例后，您可以添加其他人（分支）

于 2012-09-30T08:36:36.967 回答