使用堆栈的Java迷宫浏览器

Question

不要求代码

我只想说清楚，我不希望任何人给我解决这个问题的代码，我想自己写，这样我实际上学到了一些东西。

不要求代码

好的，所以我需要创建一个类，它将采用一个txt文件，该文件具有一个由（'W' = WALL，'S' = START，'O' = 可遍历空间，'F' = FINISH）组成的迷宫，并返回一个布尔真/假，说明迷宫是否可以使用堆栈和/或队列解决。

我现在处于早期阶段，所以我在想...

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

你喜欢这个工作吗？如何创建二维阵列？

编辑：

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

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

我建议使用数组列表

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

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

最终情况是，要么您访问 F 并获胜，要么您的堆栈完全清空，然后您知道 F 是无法访问的（因为到那时，您将从 S 访问每个可访问的节点）。

Answer 2

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

可以通过考虑其邻近指数并评估三件事来找到孩子：

> < li >此相邻索引是父索引吗？如果是，则不添加到子代 < li >相邻索引是否在迷宫的边界内？避免ArrayIndexOutofBounds异常 < li>

此节点的值等于" 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制作一个新点并将其添加到队列中，然后生成它的子级获取子级并将它们添加到队列中。添加逻辑以检查是否等于“F”