1

我正在尝试使用下面的 sudo 代码使用左手退出规则来解决迷宫我已经让它大部分工作但是我遇到了让它在遇到死胡同并回来时选择新方向的问题（就像在在第一阶段顶部为真但左、下和右壁为假的正方形的情况下，我的代码正确地从说是否输入左到底部或右侧的 2 中的任何一个，但是当它返回时它选择左侧方向而不是底部，我如何让它选择底部）。

有人可以建议我如何选择新方向 - 我已经在有问题的方法周围加上双星号 (**) 以供您参考提前感谢

Set int entr to LEFT;
Set int exit to-1;
Set boolean backtrack to false;
Set currentSquare to startingSquare;
Set previousSquare to null;
Set currentSquare.onpath to true;
While (currentSquare != endingSquare) {
    **Set exit to currentSquare.getLeftHandExit(entr);**
    Set previousSquare to currentSquare;
    Set currentSquare to currentSquare.adjacentSquare(exit);
    If (backtracking is false and exit is same as entrance)
        Set backtracking to true;
        Remove previousSquare from path;
    }
    Else if backtracking is true and currentSquare is not on the path
        Set backtracking to false;
        Add previousSquare to path;
    }
    If backtracking is true, remove currentSquare from path;
    else add currentSquare to path;
    entr = currentSquare.oppositeSide(exit);
} // end of While
4

2 回答 2

1

使用回溯系统；无论是使用递归方法（不是优选的）还是堆栈来回退步骤。理想情况下，您还会在算法选择进入的每个路口设置标记，这样您就不会再次选择相同的路径（仅选择给定路口中未标记的路径）

维基百科有一些很好的伪代码来说明如何实现这一点。注意“递归回溯”算法，将“随机选择未访问的邻居之一”替换为“从未访问的邻居之一中选择左转”（意思是从左侧单元格中顺时针选择）。

另外，请查看这本关于递归的电子书。

我会选择类似（未经测试的代码）：

maze.clearAllVisited();
Stack<Point> paths = new Stack<Point>();
int x = maze.getStartX();
int y = maze.getStartY();
while (!maze.isExit(x, y)) {
   maze.setVisited(x, y);
   if (maze.canGoWest(x, y)) {    // check if west cell is accessible from x,y and has not been visited
      paths.push(new Point(x, y));
      x--;
   } else if (maze.canGoNorth(x, y)) { // check if north cell is accessible from x,y and has not been visited
      paths.push(new Point(x, y));
      y--;
   } else if (maze.canGoEast(x, y)) {  // ...
      paths.push(new Point(x, y));
      x++;
   } else if (maze.canGoSouth(x, y)) { // ...
      paths.push(new Point(x, y));
      y++;
   } else {
      if (paths.isEmpty()) {
         break;  // no more path for backtracking, exit (aka no solution for maze)
      }
      // dead end! go back!
      Point last = stack.pop();
      x = last.x;
      y = last.y;
   }   
}
于 2010-12-06T02:33:05.160 回答
1

如果你总是向左转，那么就转身，你应该改变方向，所以你的左边变成了右边。

当你到达下一个走廊时，你仍然会左转。

我认为它只是将您的左手放在墙上，您最终会找到出路。

根据您的迷宫的复杂程度，可以设计一个迷宫，最终您将进入循环，因此您可能想要更改您所在位置的颜色，以便您可以检测到您何时通过某个部分的双向，或者我再次重复你的路径。

于 2010-12-06T02:45:24.030 回答