使用堆栈遍历并解决迷宫 – Java
所以我正在尝试创建一个迷宫求解器程序，它可以解决X和O的迷宫问题。 我想要做的是创建一个Point类，这样我就可以创建一个二维点数组，这将允许打印到输出页面以及实现堆栈相对简单。
我想在实际程序中实现的最简单的一般思想算法我认为应该是：
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类位于其中。 我知道对于Point我应该设置X坐标，并设置Y坐标以及两者的getter。 你认为我需要比这两种更多的方法吗？ 比如，我应该创建一个传递x坐标的方法，并将y坐标作为参数，这样我就可以将它们作为一个一起推送，而不是单独设置x和y？
这是一个样本迷宫的样子，你从右下角开始尝试遍历左上角，X为墙壁，O为迷宫中的开放空间：
OOOOOXO XXOXOOX OXOOXXX XXXOOXO XXXXOOX OOOOOOOXXOXXXO
你确定你的算法可以解决任何迷宫吗？ 我认为它会陷入这个简单的模型（S开始，F完成）：
xxxxxxxxxx Sooooooxxx xxxxxxoxxx xxxxxxFxxx
你的算法将沿着第一个大厅向下行进，直到它面临跌倒，向左转，面向“北”墙，再次向左转，然后走回第一个走廊，在那里它将再次向左转两次并继续重复这个问题。
右手规则算法（参见维基百科页面 ，以及更多迷宫算法的其他部分）应该解决任何没有循环的迷宫，并且应该相当容易在java中实现。
你可以用一个
Stack 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);
对于算法部分，优选通过堆栈的深度优先递归。 有点像：
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 // }
你需要你的点类返回每个给定方向的下一个点（向后除外），以及检测你何时处于迷宫的边缘。 您可能想要一个包含所有点的Maze类，打印，存储X / O等等。因此，您可以使用currentSpot = Maze.getStartingSpot（）替换初始currentSpot =（0,0） ;
对于您的算法，您不需要堆栈。 只有在使用回溯来撤消遍历决策时，才需要堆栈。
对于算法，你可以使用回溯 （ 编辑，虽然它不太符合你的一般想法。）你只需要意识到你的动作被“推”到一个虚拟堆栈中，它们必须被拔掉（因此被撤消。）你可能如果“机器人”是一个实际移动的对象，你必须自己实现堆栈，但如果你只想解决迷宫，你可以依赖于调用堆栈。
使用墙跟随算法： http ： //en.wikipedia.org/wiki/Maze_solving_algorithm#Wall_follower
我在学校时曾经解决过这个问题，我们使用了类似于左/右手规则的解决方案。 我相信我们在学习链接列表时这样做了。 简而言之，算法是这样的：
- 往左走。 如果可能，重复一遍。
- 如果没有，请直接进行。 如果可能，请返回步骤1。
- 如果没有，请转右。 如果可能，请返回步骤1。
在每一步，您还要检查您所站立的位置是否完成。 如果您无法继续（即无法向左，向右或向右），则将您所站立的位置标记为“已访问”并备份。 冲洗并重复。