我的迷宮檢查器有什麼問題？ （JAVA）

Question

所以我們給了一個迷宮與牆壁（W）開放路徑（O）一個開始點（S）和完成點（F）。

我想寫一個算法，需要迷宮文件，然後把它變成一個二維數組的點，使網格。

一旦我有了網格，我想從迷宮中的'S'角色開始，並試圖找出是否有可能遍歷O到達F.（返回布爾真/假）

我知道這個迷宮是可以解決的，所以我爲什麼會'假'？必須有一個複雜的問題，因爲我得到的是純布爾值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分鐘內就寫到這，讓我知道是否有錯誤。

EDIT（相對於OP的編輯）：

你canMove<direction>方法太複雜，實際上沒有必要做出Ø這樣的功能，更談不上檢查堆棧。另外，你的traverseMaze函數應該在起始位置採用一行和一列的參數，或者你應該把這些信息放在你的類中作爲私有變量。

簡單地做這樣的事情

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

現在你需要做的就是把到以上提供的算法的循環，它應該工作。請注意，我將數組中的當前點標記爲「已訪問」行，並將其標記爲「將鄰居標記爲已訪問」，因爲檢查堆棧內的點是否存在效率不高。將它們標記爲已訪問。進棧不過，你仍然需要標記你的起始位置，當你開始你的循環

Answer 2

另一個使用堆棧想參觀

僞代碼：

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 3

你問你的問題的意見如何找到起點。您可以在啓動迷宮點陣列時找到起點

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

初始化後，請按照上面提供的算法之一進行操作。