java - Java 中的迷宫求解器问题

Question

我现在已经让它停止无限重复，但它只是一遍又一遍地尝试相同的错误路径。有谁知道有什么方法让它尝试不同的路径吗？

数字键:0 已开放1是一堵墙2 是路径的一部分3是迷宫的尽头

    public class Maze{
  public static void main(String[] args){
    int[][] maze = {{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
      {0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1},
      {1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1},
      {1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,1},
      {1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1},
      {1,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1},
      {1,0,1,1,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1},
      {1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,1},
      {1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1},
      {1,0,1,0,1,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,1},
      {1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,1,1},
      {1,0,1,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1},
      {1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1},
      {1,0,1,0,1,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1},
      {1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1},
      {1,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,1},
      {1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1},
      {1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,1},
      {1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1},
      {1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1},
      {1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1},
      {1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,1,0,1},
      {1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1},
      {1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1},
      {1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1},
      {1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,1},
      {1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,0,1},
      {1,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,0,0,1,0,1,0,1},
      {1,0,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,1,1,1,1,0,1},
      {1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,1},
      {1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1},
      {1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1},
      {1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1},
      {1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1},
      {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1}};
    boolean[][] posCheck = new boolean[maze.length][maze[0].length];
    int r = 0;
    int c = 0;
    for(int row = 0; row < maze.length; row++){
      for(int col = 0; col < maze[row].length; col++){
        if(maze[row][col]==0){
          r = row;
          c = col;
        }
      }
    }
    maze[r][c] = 3;
    mazeSolver(1, 0, maze, posCheck);
  }

  public static boolean mazeSolver(int r, int c, int[][]maze, boolean[][] posCheck){
    posCheck[r][c] = true;
    maze[r][c] = 2;

    if(maze[r][c] == 3){
      print(maze);
      return true;
    }

    if((c+1 < maze.length) && maze[r][c+1]==0 && !posCheck[r][c+1] && (mazeSolver(r, c + 1, maze, posCheck))){
      maze[r][c] = 2;
      return true;
    }

    if((r-1 >= 0) && maze[r-1][c]==0 && !posCheck[r-1][c] && (mazeSolver(r - 1, c, maze, posCheck))){
      maze[r][c] = 2;
      return true;
    }

    if((c-1 >= 0) && maze[r][c-1]==0 && !posCheck[r][c-1] && (mazeSolver(r, c - 1, maze, posCheck))){
      maze[r][c] = 2;
      return true;
    }

    if((r+1 < maze.length) && maze[r+1][c]==0 && !posCheck[r+1][c] && (mazeSolver(r + 1, c, maze, posCheck))){
      maze[r][c] = 2;
      return true;
    }

    print(maze);
    return false;
  }

  public static void print(int[][] maze){
    for(int row = 0; row<maze.length; row++){
      for(int col = 0; col<maze[row].length; col++)
        System.out.print(maze[row][col]);
      System.out.println();
    }
  }
}

Answer 1

我已将调试输出添加到您的 mazeSolver 函数中的每个分支。正如您所看到的，没有分支被调用，因为第三个 if block 中的递归调用永远不会完成评估。因此，它是无限递归，这就是 StackOverflowError 的原因。它还表明它仅在两个不同的值之间来回跳动，这可能是一个问题。

您需要确定您的 mazeSolver 实际上在做什么 - 为什么无限递归永远不会展开，并更改它以满足其他条件之一。

换句话说，您需要修复“递归终止符”，并找出为什么除了 [1, 1] 和 [0, 1] 之外没有其他值被传递。

public static boolean mazeSolver(int r, int c, int[][] maze){
System.out.println("mazeSolver(" + r + ", " + c + ", maze)");

   if(maze[r][c] == 3)  {
System.out.println("  Equals 3 -- return true");
      return true;
   }  else if((c+1 < maze.length) && maze[r][c+1]==0 && (mazeSolver(r, c + 1, maze)))  {
      maze[r][c] = 2;
System.out.println("  Set to 2 (a) -- return true");
      return true;
   }  else if((r-1 >= 0) && maze[r-1][c]==0 && (mazeSolver(r - 1, c, maze)))  {
      maze[r][c] = 2;
System.out.println("  Set to 2 (b) -- return true");
      return true;
   }

System.out.println(" Between first and second if-block");


   if((c-1 >= 0 && maze[r][c-1]==0) && (mazeSolver(r, c - 1, maze)))  {
      maze[r][c] = 2;
System.out.println("  Set to 2 (c) -- return true");
      return true;
   }

System.out.println(" Between second and third if-block");

   if((r+1 < maze.length) && maze[r+1][c]==0 && (mazeSolver(r + 1, c, maze))){
      maze[r][c] = 2;
System.out.println("  Set to 2 (d) -- return true");
      return true;
   }

System.out.println("  return false");
   return false;
}

}

输出:

[R:\jeffy\programming\sandbox\xbnjava]java Maze
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
 Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
 Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
 Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
 Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
 Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
 Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
 Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
 Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
 Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
 Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
 Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
 Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
 Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
 Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
 Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
 Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
 Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
 Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
 Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
 Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
 Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
 Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
 Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
 Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
 Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
 Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
 Between first and second if-block

...等等...

mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
 Between first and second if-block
mazeSolver(1, 0, maze)
mazeSolver(1, 1, maze)
 Between first and second if-block
Exception in thread "main" java.lang.StackOverflowError
        at sun.nio.cs.SingleByte.withResult(Unknown Source)
        at sun.nio.cs.SingleByte.access$000(Unknown Source)
        at sun.nio.cs.SingleByte$Encoder.encodeArrayLoop(Unknown Source)
        at sun.nio.cs.SingleByte$Encoder.encodeLoop(Unknown Source)
        at java.nio.charset.CharsetEncoder.encode(Unknown Source)
        at sun.nio.cs.StreamEncoder.implWrite(Unknown Source)
        at sun.nio.cs.StreamEncoder.write(Unknown Source)
        at java.io.OutputStreamWriter.write(Unknown Source)
        at java.io.BufferedWriter.flushBuffer(Unknown Source)
        at java.io.PrintStream.write(Unknown Source)
        at java.io.PrintStream.print(Unknown Source)
        at java.io.PrintStream.println(Unknown Source)
        at Maze.mazeSolver(Maze.java:64)
        at Maze.mazeSolver(Maze.java:82)
        at Maze.mazeSolver(Maze.java:69)
        at Maze.mazeSolver(Maze.java:82)
        at Maze.mazeSolver(Maze.java:69)
        at Maze.mazeSolver(Maze.java:82)
        at Maze.mazeSolver(Maze.java:69)
        at Maze.mazeSolver(Maze.java:82)
        at Maze.mazeSolver(Maze.java:69)
        at Maze.mazeSolver(Maze.java:82)
        at Maze.mazeSolver(Maze.java:69)
        at Maze.mazeSolver(Maze.java:82)
        at Maze.mazeSolver(Maze.java:69)
    at Maze.mazeSolver(Maze.java:82)

...等等...