使用栈遍历解迷宫——Java
所以我正在尝试创建一个迷宫求解程序来解决 X 和 O 的迷宫.我想做的是创建一个点类，这样我就可以创建一个二维点数组，这将允许打印到输出页面以及实现堆栈相对简单.
So I am trying to create a maze solver program that would solve a maze of X's and O's. What I would like to do is create a class of Points, so that I can create a 2-Dimensional array of Points which would allow printing to an output page as well as implementing the stack to be relatively simple.
我想在实际程序本身中实现的一般思想的最简单算法我认为应该是:
The simplest algorithm of the general idea I'd like to implement in the actual program itself I believe should be:
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 坐标以及两者的吸气剂.你认为我需要比这两个更多的方法吗?比如，我是否应该创建一个传递 x 坐标和 y 坐标作为参数的方法，这样我就可以将它们作为一个整体推在一起，而不是单独设置 x 和 y?
But I'm having trouble coming up with a more in-depth algorithm, as well as getting my Points class situated. I know for Points I should have set X coordinate, and set Y coordinate as well as getters for the two as well. Do you think I need more methods than those two? Like, should I create a method that is passes an x coord, and y coord as parameters so I can just push those together as one, instead of setting x and y individually?
这是一个示例迷宫的样子，从右下角开始，然后尝试遍历左上角，X 为墙，O 为迷宫中的空地:
This is what a sample maze would look like, where you start in the bottom right and try to traverse to the top left, with X's as walls, and O's as open spaces in the maze:
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
推荐答案
你确定你的算法能解决任何迷宫吗?我认为它会卡在这个简单的模型中(S 是开始，F 是结束):
Are you sure your algorithm would solve any maze? I think it would get stuck in this simple mock-up (where S is start and F is finish):
xxxxxxxxxx
Sooooooxxx
xxxxxxoxxx
xxxxxxFxxx
你的算法会沿着第一个走廊向下走，直到它面对秋天，左转，面对北"墙，再次左转，然后走回第一个走廊，在那里它会再次左转两次并不断重复这个问题.
Your algorithm would proceed down the first hall until it faced the fall, turn left, be facing the "north" wall, turn left again, and walk back down the first hallway, where it would turn left twice again and keep repeating this problem.
右手法则算法(参见维基百科页面，以及更多迷宫算法的其他部分)应该可以解决任何没有循环的迷宫，并且应该很容易在 java 中实现.
The the right-hand rule algorithm (see the wikipedia page, as well as other sections for more maze algs) should do solve any maze without loops, and should be fairly easy to implement in java.
相关文章