陣列的迷宮算法不存儲正確的價值觀

Question

我把一切都回到了自己的迷宮求解器，除了事實wasHere陣列存儲解決方案（這是應該由correctPath陣列存儲）。它也缺少標記迷宮的末端廣場。所有wasHere陣列應該存儲的是程序在迷宮中所走過的景點。 correctPath數組具有所有錯誤值，這是完全意外的。我正在使用維基百科提到的遞歸方法：https://en.wikipedia.org/wiki/Maze_solving_algorithm

這是我迷宮求解：

private static int[][] maze = {{2, 2, 2, 2, 1, 2, 2}, 
           {2, 2, 2, 2, 1, 2, 2}, 
           {2, 2, 2, 2, 1, 2, 2}, 
           {2, 1, 1, 1, 1, 1, 1}}; // The maze 
private static boolean[][] wasHere = new boolean[4][7]; 
private static boolean[][] correctPath = new boolean[4][7]; // Solution 

private static int startX = 4; 
private static int startY = 0; 

private static int endX = 1; 
private static int endY = 3; 

public static void main(String[] args) { 
    System.out.println("Maze: "); 
    printMaze(maze); 

    solveMaze(); 

    boolean b = recursiveSolve(startX, startY); // Whether or not there is a solution to the maze 
} 

public static void solveMaze() 
{ 
    for (int row = 0; row < maze.length; row++) 
    { 
     // Sets boolean arrays to false 
     for (int col = 0; col < maze[row].length; col++) 
     { 
      wasHere[row][col] = false; 
      correctPath[row][col] = false; 
     } 
    } 
} 

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

      if (col == array[row].length - 1) 
      { 
       System.out.print("\n"); 
      } 
     } 
    }  

    System.out.print("\n"); 
} 

public static void printPath(boolean[][] array) 
{ 
    for (int row = 0; row < array.length; row++) 
    { 
     for (int col = 0; col < array[row].length; col++) 
     { 
      if (array[row][col] == true) 
      { 
       System.out.print("1"); 
      } 
      else 
      { 
       System.out.print("2"); 
      } 

      if (col == array[row].length - 1) 
      { 
       System.out.print("\n"); 
      } 
     } 
    } 
} 

public static boolean recursiveSolve(int x, int y) 
{ 
    if (x == endX && y == endY) // Reach end 
    { 
     System.out.println("The maze is solvable."); 
     printPath(wasHere); 
     return true; 
    } 

    if (maze[y][x] == 2 || wasHere[y][x] == true) // Hit a dead end or end up in same place (no solution) 
    { 
     return false; 
    } 

    wasHere[y][x] = true; 

    if (x != 0) // On left edge or not 
    { 
     if (recursiveSolve(x - 1, y)) 
     { 
      correctPath[y][x] = true; 
      return true; 
     } 
    } 

    if (x != maze[0].length - 1) // On right edge or not 
    { 
     if (recursiveSolve(x + 1, y)) 
     { 
      correctPath[y][x] = true; 
      return true; 
     } 
    } 

    if (y != 0) // On top edge or not 
    { 
     if (recursiveSolve(x, y - 1)) 
     { 
      correctPath[y][x] = true; 
      return true; 
     } 
    } 

    if (y != maze.length - 1) // On bottom edge or not 
    { 
     if (recursiveSolve(x, y + 1)) 
     { 
      correctPath[y][x] = true; 
      return true; 
     } 
    } 

    System.out.println("The maze is not solvable."); 
    return false; 
} 

Answer 1

迷宮，解算器是否正常工作。問題是，您可能正在打印correctPath數組的值，然後您的遞歸方法寫完了。

我認爲，你有recursiveSolve(int x, int y)方法內以下行：

System.out.println("The maze is solvable."); 
    printPath(wasHere); 

...在某些時候，你嘗試過使用correctPath變量，而不是，從右到運行呢？像這樣？

System.out.println("The maze is solvable."); 
    printPath(correctPath); 

但是這個太快了。將correctPath數組值設置爲後遞歸調用從迷宮結束開始返回。

相反，嘗試頂級呼叫移動電話printPath後到recursiveSolve方法你main()內。就像這樣：

public static void main(String[] args) { 
    System.out.println("Maze: "); 
    printMaze(maze); 

    solveMaze(); 

    boolean b = recursiveSolve(startX, startY); // Whether or not there is a solution to the maze 

    // Put this here! It will work as expected. 
    System.out.println(); 
    printPath(correctPath); 
} 

如果這並不完全對你有意義，那麼它很可能意味着你還沒有完全掌握遞歸是如何工作的。正如你應該首先完成的那樣，使用調試器遍歷你的程序，事情應該變得更加清晰。