java - 我的迷宫检查器有什么问题？？？ (Java)

Question

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

我正在尝试编写一种算法，该算法采用迷宫文件，然后将其转换为二维点数组以制作网格。

一旦有了网格，我想从迷宫中的“S”字符开始，并尝试找出是否可以遍历 O 到达 F。(返回 boolean 值 true/false )

我知道这个迷宫是可以解决的，那为什么我会得到“错误”？一定有一个复杂的问题，因为我得到的只是简单的 boolean 值 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

算法如下:

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 的编辑):

你的 canMove<direction>方法太复杂了，其实没必要做这样的函数，更不用说查栈了。此外，您的 traverseMaze 函数应该接受起始位置的 row 和 col 参数，或者您应该将此类信息作为私有(private)变量放入类中。

简单地做一些类似的事情

//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

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