用二维数组解决迷宫问题。 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; 
    } 
}