我的迷宫检测器怎么了？??(JAVA)

Question

所以我们有一个迷宫，有墙(W ),开放路径(O ),起点点(S)和终点点(F)。

我试图编写一个算法，采取迷宫文件，然后把它变成一个二维数组的点，使网格。

一旦我有了网格，我想从迷宫中的“S”字符开始，并尝试找到是否有可能穿过“O”到达“f”。(返回布尔值true/false)

我知道这个迷宫是可以解决的，那么为什么我得到了“假”？？一定有一个复杂的问题，因为我得到的只是简单的布尔假，而不是“对不起，迷宫不可穿越”...

以下是Maze1.txt文件：

WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
WSOOOOOOOOOOOOOOWOOOOOOOOOOOOOOOOOWOOOOOOOOOOOOOOOWOOOOOOW
WWOOOOOOOOOOOOOWWWWWWWWWWWWWOOOOOOOOOOWWWWWWWWWWWWWOOOOOOW
WWWWWWOOOOOOOOOOOOWWWWWWWOOOOOOOOOOOOWWWWWWWWWWWWWWWWOOOOW
WOOOOOOWWWWWWWWWWWWWWOOOOOOOOOOOWWWWWWWWOOOOOOOOOOOOOOOWWW
WOOOOWWWWWWWOOOOOOWWWWOOOOOOWWWWWWWWWWWOOOOWWWWWWWWWOWWWWW
WOOOWWWWWWWWWWWWOOWWWWWWWWWWWWOOOOOOOOOOOOWWWWWWWWWOOOOOWW
WOOWWWWWWWWWWWWWOOWWWWWWWWWWWWWWWWWOOOOOOOWWWWWWWWWWWWOOOW
WOWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWOOOOOOOWWWWWWWWWWWOOW
WOWWWWWWWWWWWWWOOOOOOOOOOOOOOOOOOOOOOOOOOOOWWWWWWWWWWWWOOW
WOOOOOOOOOOOOOOOOWWWWOOOOOOOOWWWWWWWOOOOOOWWWWWWWWWWWWWOFW
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW

这是我的代码（新尝试）：

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

public class MazeExplorer {
    static Point startPoint = new Point();
    static Point finishPoint = new Point();
    final static int mazeHeight = 12;
    final static int mazeWidth = 58;
    static char[][] mazePoints = new char[mazeHeight][mazeWidth];
    Stack<Point> pointsNotTraversed = new Stack<Point>();
    Point pt = new Point();
    static HashSet<Point> previousLocations = new HashSet<Point>();
    static Stack<Point> nextPoints = new Stack<Point>();

    public static void main(String[] args) throws FileNotFoundException{

        System.out.println("Please enter the file name of your Maze");
        Scanner console = new Scanner(System.in);
        File f = new File(console.nextLine());
        Scanner sc = new Scanner(f);

        if(!sc.hasNextLine()){
            System.out.println("Sorry, please enter a file name with the extension, that contains a maze!");
        }
        System.out.println("So, you want to know if your maze is solvable.....?");

        for (int row = 0; row < mazeHeight && sc.hasNext(); row++) {
            final String mazeRow = sc.next(); //Get the next row from the scanner.
            mazePoints[row] = mazeRow.toCharArray(); //Convert the row into a char[].
        }
            //identify the finish point
        for(int i = 0; i < mazeHeight; i++){
            for(int j = 0; j<mazeWidth; j++){
                if(mazePoints[i][j] == 'F'){
                    finishPoint = new Point(i, j);
                }       
            }
        }
        // Identify the start point
       for(int i = 0; i< mazeHeight; i++){
           for(int j = 0; j < mazeWidth; j++){
               if(mazePoints[i][j] == 'S'){
                 startPoint = new Point(i , j);
               }
           }
       }
       isTraversable(startPoint);    
    }
        public static  boolean isTraversable(Point current){
            boolean isSolvable = false;
            do {
                mazePoints[current.x][current.y] = ' ';

                if (mazePoints[current.y - 1][current.x] == 'O'){ //up dir
                   nextPoints.push(new Point(current.y - 1, current.x));
                    mazePoints[current.y - 1][current.x] = ' ';  //'X' marks where you've already been          
                }
                if(mazePoints[current.y + 1][current.x] == 'O'){ // below direction
                    nextPoints.push(new Point(current.y + 1, current.x));
                    mazePoints[current.y + 1][current.x] = ' ';        
                }
                if(mazePoints[current.y][current.x + 1] == 'O'){ // to the right
                    nextPoints.push(new Point(current.y, current.x + 1));
                    mazePoints[current.y][current.x + 1] = ' ';
                }
                if(mazePoints[current.y][current.x - 1] == 'O'){ // to the left
                    nextPoints.push(new Point(current.y, current.x - 1));
                    mazePoints[current.y][current.x - 1] = ' ';             
                }
                if(mazePoints[current.y][current.x] == 'F'){
                    isSolvable = true;
                    System.out.println("MAZE IS SOLVABLE, YAHOOOOOO!!!!");
                }
                current = nextPoints.peek();
                nextPoints.pop();
                isTraversable(current);         
            } while(!current.equals('F') && !nextPoints.isEmpty());         
            return isSolvable;          
        }
}

Answer 1

使用堆栈的另一个想法。

伪代码:

push starting point to path stack
lastStepValid = true
while (stack is not empty && goal not found) {
  lastStep = peek the top of path stack


  if (lastStep == goal) {
      goal found = true
  } else if (not lastStepValid) {
    leave last step poped
    if (path stack is not empty) {
      pop path stack
      lastStepValid = true
      if (lastStep is UP of top of path stack) {
          push RIGHT of top of path stack to path stack 
      } else if (lastStep is RIGHT of top of path stack) {
          push DOWN of top of path stack to path stack
      } else if (lastStep is DOWN of top of path stack) {
          push LEFT of top of path stack to path stack
      } else {
          lastStepValid = false
      }
    }
  } else if (lastStep is wall || lastStep exists more than once in the stack) {
      lastStepValid = false;
   } else {  // last step is valid
      push the UP of lastStep to path stack
   }
}

简而言之，你有一个堆栈来存储你走过的路径，并尝试按向上、向右、向下、向左的顺序走每一步。

这种方法不需要你在迷宫中标记细胞。

Answer 2

您在问题的评论中询问了如何找到起点。您可以在启动mazePoints阵列时找到起点

    Stack<Point> stack = new Stack<Point>();
    Point start;
    File f = new File("Maze1.txt");
    final Scanner sc = new Scanner(f);
    for (int row = 0; row < mazeHeight && sc.hasNext(); row++) {
      final String mazeRow = sc.next(); //Get the next row from the scanner.
      mazePoints[row] = mazeRow.toCharArray(); //Convert the row into a char[].
      for (int i = 0; i < mazeRow.length(); i++) {
        if (mazeRow.charAt(i) == 'S') {
          start = new Point(row, i);
          stack.push(start);
          break;
        }
      }
    }

初始化后，遵循上面提供的算法之一。

Answer 3

这是算法：

do
    mark current spot in the array as "visited" (can use any symbol you want)
    push all of the neighbors not yet visited onto the stack
    current spot <-- top of the stack to visit the next spot
    pop the stack
while (exit is not found && stack is not empty)

刚刚在5分钟内写了这个，让我知道是否有错误。

编辑(相对于OP的编辑):

您的＜代码＞可以移动

简单地做类似的事情

//assuming that current spot is at r,c
if (mazePoints[r-1][c] == 'O'){ //up dir
    pointsInMaze.push(new Point(r, c));
    mazePoints[r-1,c] = '';  //empty char marks where you've already been
}
//other directions ommitted here

现在您所要做的就是将上述内容放入提供的算法中的循环中，它应该可以工作。请注意，我在这里将“将数组中的当前点标记为‘已访问’行”更改为“将邻居标记为已访问”，因为检查堆栈内是否存在一个点效率不高。在将它们推入堆栈时将它们标记为已访问要容易得多。但是，当您开始循环时，您仍然需要将您的起始位置标记为已访问