What's wrong with my maze checker??? (JAVA)

问题:

So we are given a maze with walls(W) open path(O) a start pt (S) and a finish pt (F).

I am trying to write an algorithm that takes the maze file and then turns it into a 2D array of points to make a grid.

Once I have the grid, I want to start on the 'S' character in the maze and try to find whether or not it is possible to traverse through the O's to get to the F. (Return a boolean true/false)

I know that this maze is solvable, so why am I getting 'false'?? There must be a complicate problem because all I get is the plain boolean false, not the "sorry, maze isnt traversable"...

Here is the Maze1.txt file:

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

Here is my code(new attempt):

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;          
        }
}

回答1:

Here's the algorithm:

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)

Just wrote this in 5 min, let me know if there are bugs.

EDIT (with respect to OP's edit):

Your canMove<direction> methods are too complicated, there's actually no need o make such functions, much less check the stack. Also, either your traverseMaze function should take in a row and col argument for the starting position, or you should put such information inside your class as private variables.

Simply do something like

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

Now all you have to do is put the above into the loop in the algorithm provided and it should work. Note that I changed the "mark current spot in the array as 'visited' line to "mark neighbors as visited" here because checking whether a point exists inside the stack is not efficient. Much easier to just mark them as visited as you push them into the stack. However, you still need to mark your starting position as visited when you begin your loop

回答2:

You asked in the comments of your question how to find the starting point. You can find the starting point during the initiation of your mazePoints array

    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;
        }
      }
    }

After initialization, follow one of the algorithms that are provided above.

回答3:

Another thought using a stack.

psuedo code:

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

in brief, you have a stack to store the path you have walked, and try every step in the sequence of up, right, down left.

This approach doesn't require you to flag cells in the maze.