Maze solver java

Question

Мне нужно написать программу решения лабиринтов для APCS, которая включает в себя текстовую матрицу из них и нули. Я должен написать код, который находит путь, если он есть, от координаты 0,0 до любой точки справа. Вот то, что я до сих пор

public class Maze { 
    private int[][] maze; 
    private int sizes = 0; 
    private boolean[][] checked; 

    public Maze(int size, String line) { 
     checked = new boolean[size][size]; 
     sizes = size; 
     out.println(sizes - 1); 
     Scanner joe = new Scanner(line); 
     maze = new int[size][size]; 
     for (int x = 0; x < size; x++) { 
      for (int y = 0; y < size; y++) { 
       maze[x][y] = joe.nextInt(); 
      } 
     } 
    } 

    public boolean hasExitPath(int r, int c) { 
     boolean solved = false; 
     boolean wall = false; 

     if (r == sizes - 1) { 
      solved = true; 
      return solved; 
     } 

     maze[r][c] = 2; 
     if (maze[r + 1][c] == 1) { 
      out.println("down"); 
      hasExitPath(r + 1, c); 
     }else if (maze[r][c + 1] == 1) { 
      out.println("left"); 
      hasExitPath(r, c + 1); 
     }else if (maze[r - 1][c] == 1) { 
      out.println("up"); 
      hasExitPath(r - 1, c); 
     }else if (maze[r][c - 1] == 1) { 
      out.println("right"); 
      hasExitPath(r, c - 1); 
     } 
     System.out.println(r + " " + c); 
     return solved; 
    } 

    public String toString() { 
     String output = ""; 
     for (int y = 0; y < sizes; y++) { 
      for (int x = 0; x < sizes; x++) { 
       output = output + maze[y][x]; 
      } 
      output = output + "\n"; 
     } 
     return output; 
    } 
} 

Вот главный класс

public class MazeRunner { 
    public static void main(String args[]) throws IOException { 
     Scanner mazeinfo = new Scanner(new File("maze.dat")); 

     int size = mazeinfo.nextInt(); 
     mazeinfo.nextLine(); 
     String b = mazeinfo.nextLine(); 
     Maze m = new Maze(size, b); 
     out.println(m); 
     out.println(m.hasExitPath(0, 0)); 

     size = mazeinfo.nextInt(); 
     mazeinfo.nextLine(); 
     b = mazeinfo.nextLine(); 
     m = new Maze(size, b); 
     out.println(m); 
     out.println(m.hasExitPath(0, 0)); 

     size = mazeinfo.nextInt(); 
     mazeinfo.nextLine(); 
     b = mazeinfo.nextLine(); 
     m = new Maze(size, b); 
     out.println(m); 
     out.println(m.hasExitPath(0, 0)); 

     size = mazeinfo.nextInt(); 
     mazeinfo.nextLine(); 
     b = mazeinfo.nextLine(); 
     m = new Maze(size, b); 
     out.println(m); 
     out.println(m.hasExitPath(0, 0)); 

     size = mazeinfo.nextInt(); 
     mazeinfo.nextLine(); 
     b = mazeinfo.nextLine(); 
     m = new Maze(size, b); 
     out.println(m); 
     out.println(m.hasExitPath(0, 0)); 

     size = mazeinfo.nextInt(); 
     mazeinfo.nextLine(); 
     b = mazeinfo.nextLine(); 
     m = new Maze(size, b); 
     out.println(m); 
     out.println(m.hasExitPath(0, 0)); 
    } 
} 

Вот образ лабиринты, которые должны быть решены

https://drive.google.com/file/d/0BzE3Cu7SjRlNdzRHYjM4UzZkY00/view?usp=sharing

Я добавил кучу кода отладки в методе hasExitPath, чтобы помочь мне понять, что происходит. Всякий раз, когда я запускаю программу, она просто не может проследить лабиринт. Что мне нужно добавить в эту программу?

Answer 1

, вызывающий hasExitPath(r , c), всегда будет возвращать false, если только r == size - 1 не является истинным. Поскольку вы начинаете с r == 0, и size > 0 верно, код всегда будет отображаться с false. Используйте

if(hasExitPath(r + 1, c)) 
    return true; 

вместо простого вызова hasExitPath(r + 1, c);, чтобы решить эту проблему (то же самое для всех других рекурсивных вызовах hasExitPath(r , c)).

Answer 2

Я бы посоветовал против рекурсивного подхода, если лабиринт становится достаточно большим, у вас может возникнуть проблема переполнения стека. что я бы посоветовал вам сделать, это действовать в соответствии с направлением, в котором вы путешествуете, и переоценить направление, основанное на том, достигнете ли вы пересечения или тупика. я могу дать вам ссылку на некоторый код, который работает на проблему с лабиринтом, но не используя 2d-массив.