使用堆栈遍历和解决迷宫-Java

Question

所以我正试图创建一个迷宫求解程序来求解X和O的迷宫。我想做的是创建一类点，这样我就可以创建一个二维点数组，这将允许打印到输出页面，并实现相对简单的堆栈。

我想在实际程序中实现的一般想法的最简单算法应该是：

1) Move forward
2) Are you at a wall?
2a) If yes, turn left
3) Are you at the finish?
3a) If no, go to 1
3b) If yes, solved

但我很难想出一个更深入的算法，也很难找到我的Points类。我知道对于点，我应该设置X坐标，设置Y坐标，以及两者的getter。你认为我需要比这两种方法更多的方法吗？比如，我应该创建一个方法，将x坐标和y坐标作为参数，这样我就可以将它们作为一个参数推到一起，而不是单独设置x和y吗？

这就是一个样本迷宫的样子，你从右下角开始，试图遍历到左上角，X是墙，O是迷宫中的开放空间：

O O O O O X O
X X O X O O X
O X O O X X X
X X X O O X O
X X X X O O X
O O O O O O O 
X X O X X X O

Answer 1

你确定你的算法能解决任何迷宫吗？我认为它会被困在这个简单的模型中（其中S是开始，F是结束）：

xxxxxxxxxx
Sooooooxxx
xxxxxxoxxx
xxxxxxFxxx

你的算法会沿着第一个大厅往下走，直到它面对秋天，左转，面对"北"墙，再次左转，然后沿着第一个走廊往回走，在那里它会再次左转两次，并不断重复这个问题。

右手规则算法（请参阅维基百科页面，以及其他章节了解更多的迷宫算法）应该可以解决任何没有循环的迷宫，并且应该很容易在java中实现。

Answer 2

您可以使用

Stack<Point> points = new Stack<>();
// add a point
Point p = new Point(x, y);
if (points.contains(p))
   // been here before, in circles.
else
   points.add(p);

Answer 3

对于算法部分，优选通过堆栈进行深度优先递归。大致如下：

currentSpot = (0,0)  // The starting point //
while(! currentSpot.isExit()) {
  if (! currentSpot.left().isWall()) stack.push(currentSpot.left());
  if (! currentSpot.forward().isWall()) stack.push(currentSpot.forward());
  if (! currentSpot.right().isWall()) stack.push(currentSpot.right());
  currentSpot = stack.pop();  // Get the next location //
}

你会希望你的点类在每个给定的方向上返回下一个点（向后除外），并检测你何时到达迷宫的边缘。您可能想要一个包含所有点、进行打印、存储X/O等的Maze类。因此，您可能会将初始currentSpot=（0,0）替换为currentSpot=Maze.getStartingSpot（）；

Answer 4

对于您的算法，您不需要堆栈。只有当您使用回溯来撤消遍历决策时，才需要一个堆栈。

Answer 5

对于算法，您可以使用回溯（EDIT尽管它与您的总体想法不太匹配，但是，如果您只想解决迷宫问题，则可以依赖调用堆栈。

Answer 6

使用墙跟随器算法：http://en.wikipedia.org/wiki/Maze_solving_algorithm#Wall_follower

Answer 7

我上学的时候我们曾经解决过这个问题，我们使用了类似于右手/左手规则的解决方案。我相信我们是在学习链表时这样做的。简而言之，算法是这样的：

1. 向左走。如果可能，重复
2. 如果没有，就直走。如果可能，返回步骤1
3. 如果没有，请向右走。如果可能，返回步骤1

每走一步，你还要检查一下你所站的地方是否是终点。如果你无法继续（即无法向左、直行或向右），你可以将你所站的位置标记为"已访问"并后退。冲洗并重复。