迷宮求解器問題（獲取堆棧溢出錯誤）

Question

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

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

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

我知道這個迷宮是可以解決的，所以爲什麼我會得到一個StackOverFlowError ..？

這裏是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

你得到的堆棧溢出錯誤，原因如下：

public static boolean isTraversable(Point current){ 
     boolean isSolvable = false; 
     Stack<Point> dumbPoints = new Stack<>(); // visited 
     dumbPoints.push(current); // pt is now visited 
     previousLocations.add(startPoint); // starts with the 'S' point 
     while(!dumbPoints.isEmpty()){ 
      Point test = dumbPoints.pop(); 
      if(previousLocations.contains(test)){ 
       continue; // This gets called, and while loop skips to next iteration 
      } 
      /* None of this code matters right now, it never gets looked at */ 

     } // End of while loop 

     isTraversable(current); 
     return isSolvable; 
     } 

您發送startPoint到isTraversable()方法。在該方法中其被稱爲current。然後，您將current AKA startPoint放入堆棧，然後將startPoint添加到previousLocations集。

While循環運行，因爲dumbPoints不是空的（你把current AKA startPoint在那裏）。

在while循環中，您創建一個新點test並將其設置爲等於堆棧中的頂層項目（即current，AKA startPoint）。

你檢查看if(previousLocations.contains(test))是真的，它是。您將startPoint添加到之前設置的3個排隊的線上。由於它包含startPoint，它將繼續執行while循環的下一次迭代。

下次進入while循環時，堆棧爲空，因爲您彈出了其中唯一的項目（test）。所以這次while循環沒有被執行。

然後我們跳過了第二天線後while循環：

isTraversable(current); 

這一切開始我只說一遍。這會一直運行，直到您的計算機內存不足。因此你的錯誤。

意見 我會建議嘗試一種不同的方法。你昨天問了一個關於這個問題的問題，我相信和其他人建議將所有鄰近點推入堆棧。我認爲這是一個好主意。除了將當前項目推入堆棧，您可以將所有鄰近的O推入堆棧，然後在這些點上遞歸調用isTraversable方法。這將繼續下去，直到返回真或假，並且您將得到您的答案。

這可能是您可以使用的更清潔的方法之一，它與您已創建的代碼並不相距太遠。