用二維數組解決迷宮問題。 Java的。遞歸

Question

需要一些在java中解決迷宮問題的幫助。

該方案具有從文件讀出的迷宮，將其存儲到一個數組，解決它，並顯示在繪圖面板的溶液。我正在努力將它存儲到一個數組中，我真的不確定如何進入解決方案並顯示它。但是如果我可以在陣列部分獲得一些幫助以進入凹槽，我會非常感激。

下面是一個輸入文件的一個例子。我希望它適用於任何這種結構的迷宮（用+， - ，S，E和|）。前兩個數字（8,10）代表高度和寬度，行數和列數。

8 10 
+-+-+-+-+-+-+-+-+-+ 
|     | 
+ +-+-+-+ +-+-+-+ + 
| |    | | 
+ + +-+-+-+-+-+ + + 
| | |   | | | 
+ + + +-+-+-+ + + +-+ 
| | | |  | | | S| 
+ + + + +-+ + + + +-+ 
| | | |E| | | | 
+ + + +-+ +-+ + + + 
| | |   | | | 
+ + +-+-+-+-+-+ + + 
| |    | | 
+ +-+-+-+-+-+-+-+ + 
|     | 
+-+-+-+-+-+-+-+-+-+ 

這裏是我到目前爲止的代碼：

import java.util.Arrays; 
import java.util.Scanner; 
import java.io.File; 
import java.io.FileNotFoundException; 

public class MazeSolver { 

    // The name of the file describing the maze 
    static String mazefile; 
    static int width; 
    static int height; 
    public static void main(String[] args) throws FileNotFoundException { 
     if (handleArguments(args)) { 

     readMazeFile(mazefile); 
     DrawMaze.draw(); 

     if (solveMaze()) 
      System.out.println("Solved!"); 
     else 
      System.out.println("Maze has no solution."); 
     } 
     else { 
     System.out.println("The arguments are invalid."); 
     } 
    } 

    // Handle the input arguments 
    static boolean handleArguments(String[] args) { 
     if (args.length > 4 || args.length < 1) { 
     System.out.println("There are too many or too few command line arguments"); 
     return false; 
     } 
     if (args.length == 1) { 
     String mazefile = args[0]; 
     File file = new File(mazefile); 
     if (!file.canRead()) { 
      return false; 
     } 
     return true; 
     } 
     if (args.length == 2) { 
     String mazefile = args[0]; 
     File file = new File(mazefile); 
     if (!file.canRead()) { 
      return false; 
     } 
     int cellsize = Integer.parseInt(args[1]); 
     if (cellsize < 10) { 
      return false; 
     } 
     return true; 
     } 
     if (args.length == 3) { 
     String mazefile = args[0]; 
     File file = new File(mazefile); 
     if (!file.canRead()) { 
      return false; 
     } 
     int cellsize = Integer.parseInt(args[1]); 
     int borderwidth = Integer.parseInt(args[2]); 
     if (borderwidth < 5) { 
      return false; 
     } 
     return true; 
     } 
     if (args.length == 4) { 
     String mazefile = args[0]; 
     File file = new File(mazefile); 
     if (!file.canRead()) { 
      return false; 
     } 
     int cellsize = Integer.parseInt(args[1]); 
     int borderwidth = Integer.parseInt(args[2]); 
     int sleeptime = Integer.parseInt(args[3]); 
     if (sleeptime < 0 || sleeptime > 10000) { 
      return false; 
     } 
     return true; 
     } 
     return false; 
    } 

    // Read the file describing the maze. 
    static char[][] readMazeFile(String mazefile) throws FileNotFoundException { 

     Scanner scanner = new Scanner(new File(mazefile)); 
     height = scanner.nextInt(); 
     width = scanner.nextInt(); 
     int arrayHeight = 2 * height + 1; 
     int arrayWidth = 2 * width + 1; 
     char[][] mazeArrays = new char[arrayHeight][arrayWidth]; 
     while (scanner.hasNextLine()) { 
     String line = scanner.nextLine(); 
     System.out.println(line); 
     for (int row = 0; row < arrayHeight; row++) { 
      for (int col = 0; col < arrayWidth; col++) { 
       mazeArrays[row][col] = line.charAt(col); 
      } 
     } 

     } 
     return mazeArrays; 
    } 

    // Solve the maze.  
    static boolean solveMaze() { 
     return true; 
    } 
} 

我想我的命令行參數下的處理。 readMazeFile方法是我目前掙扎的地方。我無法將我的頭圍繞着存儲迷宮並解決它。

謝謝！

Answer 1

首先要做的是爲你制定一個數據結構來存儲迷宮。我建議使用一種結構，儘可能簡單地解決問題，即使打印更復雜。這裏有一個簡單的例子：

class Node { 
    private final int row; 
    private final int col; 
    private final List<Node> paths; 
} 

class Maze { 
    private final int rowCount; 
    private final int colCount; 
    private final List<Node> nodes; 
    private Node start; 
    private Node end; 
} 

在我看來，這將比類似數組更有用。一個數組可以很容易地打印迷宮，但這不是操作中最困難的部分。路徑尋找算法需要能夠輕鬆地從該數據結構允許的任何位置獲取路徑。

你問的閱讀迷宮一些幫助。我建議在Maze內使讀取方法成爲靜態的「構建器」方法。一般來說，結構是這樣的：

class Maze { 
    public static Maze buildMaze(String mazeFile) { 
     // read row & col size from file 
     Maze maze = new Maze(rows, cols); 
     // skip first line (invariant) 
     for (int row = 0; row < rows; row++) { 
      // get next 2 lines (for horizontal & vertical paths) 
      for (int col = 0; col < cols; col++) { 
       // get corresponding horizontal wall or space 
       if (isHorizontalPath) { 
        maze.getNode(row,col).addHorizontalPath(); 
       } 
       if (hasVerticalPath) { 
        maze.getNode(row, col).addVerticalPath(); 
       } 
       // check for S and E 
       if (isStart) { 
        maze.setStart(row, col); 
       } else if (isEnd) { 
        maze.setEnd(row, col); 
       } 
      } 
     } 
     return maze; 
    } 
}