递归迷宫求解器问题

Question

我正在制作一个递归Java迷宫程序，当涉及到调用我的子程序goNorth(),goWest(),goEast()和goSouth()时，我被卡在部件上。基本上我的问题涉及这样一个事实，即它调用一个子例程，但在该子例程中，它不会接受我的其他else和else语句，因此不会使它接受其他可能性。请协助，我感谢您即将到来的答案。

import java.util.*; 
import java.io.*; 

public class RecursiveMazeSolverv2 { 

    static Scanner in; 
    static int row = 0; 
    static int col = 0; 
    static char maze[][]; 
    static int rowSize = 0; 
    static int colSize = 0; 
    static boolean success = true; 

    public static void main(String[] args) { 

    while (true) { 
     try { 
     in = new Scanner(new File("Maze1.txt")); 
     break; 
     } 
     catch (FileNotFoundException e) { 
     System.out.println("Wrong File"); 
     } 
    } 
    rowSize = Integer.parseInt(in.nextLine()); 
    colSize = Integer.parseInt(in.nextLine()); 

    maze = new char[rowSize][colSize]; 

    String lineOfInput = ""; 
    for (int i = 0; i < maze.length; i++) { 
     lineOfInput = in.nextLine(); 
     for (int j = 0; j < maze.length; j++) { 
     maze[i][j] = lineOfInput.charAt(j); 
     } 
    } 

    displayGrid(); 

    for (int i = 0; i < maze.length; i++) { 
     for (int j = 0; j < maze.length; j++) { 
     if (maze[i][j] == 'S') { 
      maze[i][j]='+'; 
      System.out.println("Starting coordinates: " + i + ", " + j); 
      row = i; 
      col = j; 
     } 
     } 
    } 

if (goNorth(row, col)) 
    displayGrid(); 
else 
    System.out.println("Impossible!"); 
    } 


    static Boolean goNorth(int row, int col) { 
    if (maze[row][col] == '.') { 
     maze[row][col] = '+'; 
     return goNorth(row -1, col); 
    } 

    else if (maze[row][col] == 'G') { 
     return true; 
    } 

    else { 
     success = goNorth(row, col); 
     if (success == false) { 
     success = goWest(row, col -1); 
     } 
     if (success == false) { 
     success = goEast(row, col +1); 
     } 
     if (success == false) { 
     success = goSouth(row +1, col); 
     } 
     if (success == false) { 
     maze[row][col] = '.'; 
     success = false; } 
     return false; 
    } 

    } 
    static Boolean goWest(int row, int col) { 
    if (maze[row][col] == '.') { 
     maze[row][col] = '+'; 
     return goWest(row, col -1); 
    } 

    else if (maze[row][col] == 'G') { 
     return true; 
    } 

    else { 
    success = goWest(row, col); 
     if (success == false) { 
     success = goNorth(row -1, col); 
     } 
     if (success == false) { 
     success = goSouth(row +1, col); 
     } 
     if (success == false) { 
     success = goEast(row, col -1); 
     } 
     if (success == false) { 
     maze[row][col] = '.'; 
     success = false; } 
     return false; 
    } 

    } 

    static Boolean goEast(int row, int col) { 
    if (maze[row][col] == '.') { 
     maze[row][col] = '+'; 
     return goEast(row, col +1); 
    } 

    else if (maze[row][col] == 'G') { 
     return true; 
    } 

    else { 
    success = goEast(row, col); 
     if (success == false) { 
     success = goNorth(row -1, col); 
     } 
     if (success == false) { 
     success = goSouth(row +1, col); 
     } 
     if (success == false) { 
     success = goWest(row, col -1); 
     } 
     if (success == false) { 
     maze[row][col] = '.'; 
     success = false; } 
     return false; 
    } 

    } 


    static Boolean goSouth(int row, int col) { 
    if (maze[row][col] == '.') { 
     maze[row][col] = '+'; 
     return goSouth(row +1, col); 
    } 

    else if (maze[row][col] == 'G') { 
     return true; 
    } 

    else { 
    success = goSouth(row, col); 
     if (success == false) { 
     success = goNorth(row -1, col); 
     } 
     if (success == false) { 
     success = goWest(row, col -1); 
     } 
     if (success == false) { 
     success = goEast(row, col +1); 
     } 
     if (success == false) { 
     maze[row][col] = '.'; 
     success = false; } 
     return false; 
    } 

    } 

    public static void displayGrid() { 
    for (int j = 0; j < maze.length; j++) { 
     for (int k = 0; k < maze.length; k++) { 
     System.out.print(maze[j][k] + " "); 
     } 
     System.out.println(); 
    } 
    } 
} 

对不起，我不能在这里发布实际的迷宫，它不会显示正确。

Answer 1

问题，我看到：

1. 正如其他人躲避到，你不应该让一切static。没有进入一个超长和无聊的讨论，使所有的东西static意味着你在递归调用中设置的值将修改所有调用的值。您正在使用后续递归调用中设置的值有效地覆盖每个递归调用。您将希望使这些方法范围的变量中的大部分变量，以便该值仅在该方法调用的范围内有效。
2. 递归调用的顺序不同。您需要每次在同一步骤中执行相同的呼叫：先尝试北，然后尝试南，然后尝试东，然后尝试西。无论您选择什么命令，呼叫都需要按照相同的顺序。事实上，我不确定为什么你决定为每个方向分别使用不同的方法......为什么不能有一种方法称为“移动”，它尝试去北方，然后递归，然后尝试去南方，然后递归，然后尝试去东和递归，然后西和递归。你编写代码的方式，并不知道代码将在迷宫中的哪个位置出现，而且很可能你最终会绕着圈子走。
3. 这并不直接与它为什么不起作用直接相关，但你真的需要处理你的代码格式，特别是你的tab键。你的代码看起来像遍布整个地方。我只能想象，这使得它很难解决它需要的。

编辑 - 举例

我会尽力做到这一点的方式来指导你不给你复制/粘贴答案，所以这将是伪code'ish。

/** 
* My move recursion 
*/ 
public boolean move(int currRow, int currCol) { 
    // See if we solved it... 
    if (solved) { 
    return true; 
    } 

    // Try to go north first... 
    if (maze[currRow-1][currCol] == '.') { 
    if (move(int currRow-1, currCol)) { 
     // Mark this with the "good" path and return true 
    } 
    } 

    // Try to go east next... 
    if (maze[currRow][currCol+1] == '.') { 
    if (move(int currRow, currCol+1)) { 
     // Mark this with the "good" path and return true 
    } 
    } 

    // Try to go south next... 
    if (maze[currRow+1][currCol] == '.') { 
    if (move(int currRow+1, currCol)) { 
     // Mark this with the "good" path and return true 
    } 
    } 

    // Try to go west... 
    if (maze[currRow][currCol-1] == '.') { 
    if (move(int currRow, currCol-1)) { 
     // Mark this with the "good" path and return true 
    } 
    } 

    return false; 
} 

所以，基本上我们检查，如果我们 “解决”。如果不是，看看我们是否可以北上。如果可以的话，看下一个通话是否已经解决。重复东，南，西。最终其中一个递归调用将达到解决的条件，这将触发每个递归调用来传递内部if，这将标记迷宫并返回true，从而创建一个连锁反应，最终弹出备份调用堆栈直到你完成了递归。

事情递归注意：

1. 它通常需要一个过程，可以分解成一个或多个可重复的，自主的步骤。这并不意味着它必须是一种方法，但如果它是多种方法，您必须按照相同的顺序在方法内执行某些操作。否则，你的逻辑不同步。
2. 当您可以将“步骤”分解为最小的，最卑鄙的部分时，它通常效果最佳。过于复杂的递归方法使得难以进行调试以及大量疯狂的分支和循环。
3. 你必须有一个非常清晰的“结束”，否则你会缓慢的，直到你吹了堆栈。
4. “方法级别”的变量/数据/信息和“全局”的应该有非常明显的区别。就你而言，迷宫是全球性的，成功和现在的位置不是。