java - 递归迷宫求解器问题

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. 正如其他人所回避的那样，您不应该将所有内容都设为静态。无需进行超长且无聊的讨论，将所有内容设为静态意味着您在递归调用中设置的值将修改所有调用的值。您实际上是用您在后续递归调用中设置的值覆盖每个递归调用。您将希望创建大部分方法范围的变量，以便该值仅在该方法调用的范围内有效。
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，从而标记迷宫并返回 true，从而创建链式 react ，最终弹出调用堆栈，直到您已完成递归。

递归的注意事项:

1. 它通常需要是一个可以分解为一个或多个可重复、自主步骤的流程。这并不意味着它必须是一种方法，但如果它是多种方法，您必须以相同的顺序在方法内执行操作。否则，你的逻辑就会不同步。
2. 当您可以将“步骤”分解为最小、最琐碎的部分时，通常效果最好。过于复杂的递归方法会导致调试困难以及大量疯狂的分支和循环。
3. 你必须有一个非常明确的“结束”，否则你会递归，直到你炸毁堆栈。
4. “方法级别”的变量/数据/信息和“全局”的事物之间应该有非常明显的区别。就您而言，迷宫是全局性的，成功和当前位置则不是。