使用堆栈的Java迷宫浏览器

Question

不要求代码

我只想明确一点，我不希望任何人给我解决这个问题的代码，我想自己写，这样我就能真正学到一些东西。

不要求代码

好吧，所以我需要创建一个类，它将接收一个txt文件，该文件包含一个由('W'=WALL，'S'=START，'O'=TRAVERABLE SPACE，'F'=FINISH)组成的迷宫，并返回一个布尔值true/false，说明迷宫是否可以使用堆栈和/或队列来解决。

我现在正处于早期阶段，所以我的想法是。。。

我能以某种方式创建一个二维数组，为迷宫中的每个角色分配"坐标"吗？然后浏览每一个字母并"爆炸"，从四个方向检查它是否可以继续这样？一旦对该位置进行了探索，它将被添加到堆栈中，因此不再进行探索。

像这样的东西行吗？如何创建2D阵列？

编辑：

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.Stack;
import java.awt.Point;

public class MazeExplorer {
public static int x;
public static int y;
final int mazeHeight = 12;
final int mazeWidth = 58;
public static char[][] mazeLocationPoints = new char[12][58];



public static void main(String[] args) throws FileNotFoundException{
File f = new File("Maze1.txt");
Scanner sc = new Scanner(f);
String mazeString = new Scanner( f ).useDelimiter("\A").next();
Stack<Point> points = new Stack<>();
while(sc.hasNextLine()){
mazeLocationPoints[][] = sc.nextLine().toCharArray();
points.push(mazeLocations);

}
}
}

Answer 1

您应该将每个点视为跟踪其祖先和子节点的节点。如果子节点不是当前节点的父节点，则会将其添加到列表中，并且其值=="O"通过将起始节点添加到队列开始。将其弹出并标记为已访问。将其所有子项添加到队列中，将其弹出并标记为已访问。重复此过程，直到您的队列为空或找到值为"F"的节点

儿童可以通过考虑其相邻指数并评估三件事来找到：

1. 这个相邻索引是父索引吗？如果是，则不要添加到子项
2. 相邻的索引是否在迷宫的范围内？避免ArrayIndexOutofBounds异常

3. 此节点上的值是否等于"O"或"F"。如果"O"添加到子列表和队列中。如果"F"，则结束。

   public class Point {
   int i;
   int j;
   char value;
   Point parent;
   ArrayList<Point> children;
   public static final maze[][];
   public Point(int i, int j, char val) {
   this.i = i;
   this.j = j;
   this.val = val
   parent = null;
   children = new ArrayList<Point>();
   }
   public void generateChildren() {
   if (i + 1 <= mazeHeight && j + 1 <= mazeWidth) {
   if (maze[i+1][j+1] == 'O') {
   if (!maze[i+1][j+1].equals[this.parent]) {
   Point child = new Child(i+1, j+1, 'O');
   child.parent = this;
   children.add(child);
   }
   }
   }
   // ADD LOGIC FOR OTHER CASES i -1 j -1 etc ...  
   }
   }
   

类似的东西。开始我用Start创建一个新的Point，并将其添加到队列中，然后生成它的子项，将子项取回并添加到队列。添加逻辑以检查是否等于"F">

Answer 2

回到这里。如果你一开始不知道迷宫的大小，我不会使用2D阵列。数组在Java中是固定大小的，如果不进行昂贵的操作，就无法进行扩展。或者，你可以将你的2D阵列分配得比迷宫大，然后只填充你所拥有的。如果你知道大小，那么你在阵列使用方面是黄金。

我建议使用ArrayList>(或者使用String而不是Character，如果这对你来说更容易的话)来维护你的迷宫。这样你就可以很容易地建立你的迷宫，而不需要知道尺寸，并有一个容易的时间打印它

至于迷宫穿越，你需要记录起点，然后搜索终点。有几种算法可供选择(有些比其他算法好得多)，但如果你的老师希望你使用堆栈，他可能希望你使用深度优先搜索，因为这是标准的基于堆栈的搜索算法。维基百科上有一篇关于它如何被执行的好文章。

你还需要使用地图来维护你已经搜索过的迷宫中的位置。或者，你可以修改迷宫本身，并在访问O后填写W，但这可能会有点棘手，因为它会引入一些需要担心的边缘情况。

最终的情况是，要么你访问了F并获胜，要么你的堆栈完全清空，然后你知道F是不可访问的(因为到那时你已经访问了S中的每一个可访问节点)。