递归迷宫解算器问题

Question

我正在制作一个递归Java迷宫程序，当涉及到调用我的子例程goNorth()、goWest()、goEast()和goSouth()时，我陷入了困境。基本上，我的问题涉及到它调用一个子例程的事实，但在该子例程中，它不会接受我的另一个else-if和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. 这与它不起作用的原因没有直接联系，但您确实需要处理代码格式，尤其是选项卡。你的代码看起来到处都是。我只能想象，这会使故障排除变得更加困难

编辑-示例

我会尝试在不给你复制/粘贴答案的情况下引导你这样做，所以这将是伪代码。

/**
 * 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，内部if标记迷宫并返回true，从而产生连锁反应，最终会弹出调用堆栈，直到完成递归。

递归需要注意的事项：

1. 它通常需要是一个可以分解为一个或多个可重复的、自主的步骤的过程。这并不意味着它必须是一个方法，但如果是多个方法，则必须以相同的顺序在方法中执行操作。否则，你的逻辑就会不同步
2. 通常，当你能把"台阶"分成最小、最卑微的部分时，效果最好。过于复杂的递归方法会导致难以调试以及大量疯狂的分支和循环
3. 你必须有一个非常清晰的"结束"，否则你会重复出现，直到你把堆栈炸飞
4. 在"方法级"的变量/数据/信息和"全局"的事物之间应该有非常明确的区别。在你的情况下，迷宫是全球性的，成功和目前的地位不是