使用堆栈遍历并解决迷宫-Java [英] Using a stack to traverse and solve a maze - Java

问题描述

因此，我正在尝试创建一个迷宫求解器程序，该程序可以解决X和O的迷宫.我想做的是创建一个Points类，这样我就可以创建一个Points的二维数组，该数组将允许打印到输出页面以及实现相对简单的堆栈.

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类放置到位方面遇到了麻烦.我知道要为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.

这篇关于使用堆栈遍历并解决迷宫-Java的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！