如何使用堆栈、队列和坐标在 Java 中创建迷宫求解器?

Question

我想使用以下通用类在 Java 中创建一个迷宫求解器：队列、堆栈和坐标(存储当前 [x，y] 坐标)。程序读取包含迷宫的文本文件，将其传输到矩阵，并从起始位置搜索并移动到空白区域，直到找到最终位置。

这是文本文件：

5
8
########
E      #
### ####
### ####
###S####

由于程序中必须存在队列、堆栈和坐标泛型类，因此必须创建 4 个对象：

-类堆栈<坐标>的一个对象称为"路径"，类
堆栈<队列><坐标的一个对象>>称为"可能性"，两者都能够存储40个坐标(5 x 8 -
5行和8列);

-类队列的一个对象称为"queue"，它存储 3 个坐标，并将搜索所有 4 个方向时找到的当前位置周围的空白空间或字符"S"排队。(例如，在第一次搜索中，队列将是：[(1,1)， ， ] 因为 1,1 是从起始位置找到的第一个空白区域，然后将其添加到队列中。

-坐标类中一个名为"current"的对象，它表示当前位置。

5 表示行数。8 表示列数。字符"#"代表一堵墙，一个无法通行的地形。字符"E"是起始位置，字符"S"是出口，空白区域(字符")表示可步行空间。因此，程序首先将文本文件上的迷宫传输到具有指定行数和列数(5 和 8)的矩阵中，然后找到字符"E"，这是起始位置并实例化"当前"对象，将其坐标存储在其上(在这种情况下为 (1,0))。

从那里，它顺时针搜索当前位置周围的所有 4 个方向(按此顺序向上、向右、向下和向左)，并存储"queue"对象上找到的空白空间(或字符"S")的坐标，并从"队列"中删除第一个坐标，将此坐标存储在表示当前位置的"当前"对象上。然后，在矩阵上，在"当前"对象(坐标)表示的位置上放置一个字符"*"，表示已采取步骤。然后，将对象"当前"堆叠在"路径"对象上，并将"队列"对象堆叠在对象"可能"上。 然后重复这些步骤，直到找到出口(字符"S")，打印矩阵并关闭程序。

最后，由于每个位置都标有"*"，矩阵必须如下所示： (文本文件保持不变)。

5
8
########
E***   #
###*####
###*####
###S####

到目前为止，我已经创建了类：

队列：

public class Fila <T> {
private Object[objfila] = null;
private int quantidade,posinicial,posfinal;
public void inserir(Object x) throws Exception
{
if(quantidade==objfila.length)
throw new Exception("Queue is full");
x=objfila(posfinal);
quantidade++;
posfinal++;
}
public void remover() throws Exception
{
if(quantidade==0){
throw new Exception("there are no elements on the queue");
}
quantidade--;
posinicial++;
}
public Fila(int capacidade)
{
this.posinicial=0;
this.posfinal=0;
Object objfila=new Object();
}
}

叠：

public class Pilha <T> {
private Object[] objpilha = null;
private int topo;
public void inserir(T x) throws Exception
{
if(topo==objpilha.length-1){
throw new Exception("the stack is full.");
}
topo++;
objpilha[topo]=x;
}
public void remover() throws Exception
{
if(topo==-1){
throw new Exception("there are no elements to be removed.");
}
topo--;
}
public Pilha(int capacidade){
objpilha=new Object[capacidade];
topo=-1;
}
}

和坐标：(我认为应该有一个存储坐标的 x 和 y 数组)

public class Coordenadas <T>{
private int x;
private int y;
}

我遇到的问题是创建这些对象并将它们插入其他对象，例如将找到的坐标存储在"队列"上并将"当前"对象堆叠在"路径"对象上。制作此程序的正确方法是什么？

对不起，这个问题很长。

Answer 1

首先：Java API中有一个Stack类。Deque接口包含的比堆栈多一点。您可以启动任何实现，例如ArrayDeque：

Deque<Point> stack = new ArrayDeque<>();
stack.push(new Point(2,3));
stack.push(new Point(2,4));
Point p = stack.pop(); // (2, 4)

同样，有一个包含许多实现的Queue接口。ArrayDeque就是其中之一：

Queue<Point> queue = new ArrayDeque<>();
queue.add(new Point(1, 2));
queue.add(new Point(1, 3));
Point p = queue.remove(); // (1, 2)

我正在使用与这些令牌一起使用的Point类。

底线：您可以在此类的顶部构建迷宫求解器。因此，您可以专注于解决迷宫。java 库将处理算法细节。