使用递归在迷宫中找到最短路径？

Question

最近我一直在尝试编写一些递归迷宫代码，return是迷宫中的最短路径。如果没有穿过迷宫的路径，则代码将 return -1。

例如，对于板子：

W-S-
----
--X-

其中 S 是迷宫的起点，W 代表一堵墙，X 代表期望的目的地，- 代表可用的路径点。输出将是：2

董事会：

 -SW
 -W-
 W-X

输出将是 -1

这一切都是通过一个棋盘 class 实现的，该棋盘采用字符串和迷宫的尺寸，一个 return 最短路径的检查函数，以及一个 returns 最短路径，如果没有路径则为 -1。但是，当我运行我的代码时，第一个示例的输出为负 1，第二个示例的输出为 1。

我的代码：

棋盘Class:

  class Board
{
   private char[][] board;  
   private int maxPath = 9999;

   public Board(int rows, int cols, String line)  
   {
      char[][] board1 = new char[rows][cols];
      int z = 0;
      for(int x = 0; x < rows; x++) {
         for(int y = 0; y < cols; y++) {
            board1[x][y] = line.charAt(z);
            z++;
         }
      }
      board = board1;


   }

    /** returns the length of the longest possible path in the Board   */
   public int getMaxPath()      
   {  
      return maxPath; 
   }    

   public void display()
   {
      if(board==null) 
         return;
      System.out.println();
      for(int a = 0; a<board.length; a++)
      {
         for(int b = 0; b<board[0].length; b++)
         {
            System.out.print(board[a][b]);
         }
         System.out.println();
      }
   }

   /**  
    *  calculates and returns the shortest path from S to X, if it exists   
    *  @param r is the row of "S"
    *  @param c is the column of "S"
    */
   public int check(int r, int c)
   {    
      if(r<0||r > board.length-1||c<0||c>board[0].length-1) {
         return maxPath;
      }
      if(board[r][c] == '*') {
         return maxPath;
      }
      if(board[r][c] == 'W') {
         return maxPath;
      }
      if(board[r][c] == 'X') {
         return 0;
      }
      if(board[r][c] == '-') {
         board[r][c] = '*';
      }

      int up = 1 + check(r-1,c);
      int down = 1 + check(r+1,c);
      int left = 1 + check(r,c-1);
      int right = 1 + check(r,c+1);
      board[r][c] = '-';
      if(up < down) {
         if(up < left) {
            if(up < right) {
               return up;
            }
            else {
               return right;
            }
         }
         else {
            if(left < right) {
               return left;
            }
            else {
               return right;
            }
         }
      }
      else {
         if(down < left) {
            if(down < right) {
               return down;
            }
            else {
               return right;
            }
         }
         else {
            if(left < right) {
               return left;
            }
            else {
               return right;
            }
         }
      }


   }    

   /**  
    *  precondition:  S and X exist in board
    *  postcondition:  returns either the length of the path
    *                  from S to X, or -1, if no path exists.    
    */
   public int win()
   {
      int x = 0;
      int y = 0;
      int z = 0;
      int startRow = 0;
      int startCol = 0;
      while( x < board.length && z == 0) {
         while(y < board[0].length && z == 0) {
            if(board[x][y] == 'S') {
               z++;
               startRow = x;
               startCol = y;
            }
            y++;
         }
         x++;
      }
      System.out.println(startRow + " " + startCol);
      if(check(startRow,startCol) < maxPath) {
         return check(startRow,startCol);
      }
      else if (check(startRow,startCol) == maxPath) {
         return 1;
      }
      else {
         return -1;
      }

   }

测试用例：

public static void main(String[] args)
   {
      Board b = null;
      b = new Board(3,4,"W-S-------X-"); 
      b.display();
      System.out.println("Shortest path is " + b.win());  //2

      b = new Board(4,3,"S-W-----X-W-"); 
      b.display();
      System.out.println("Shortest path is " + b.win());  //4

      b = new Board(3,4,"X-WS--W-W---"); 
      b.display();
      System.out.println("Shortest path is " + b.win());  //7

      b = new Board(3,5,"W--WW-X----SWWW"); 
      b.display();
      System.out.println("Shortest path is " + b.win());  //1

      b = new Board(3,3,"-SW-W-W-X");     //no path exists
      b.display();
      System.out.println("Shortest path is " + b.win());  //-1

      b = new Board(5,7,"-W------W-W-WX--S----W----W-W--W---");     //Example Board 1
      b.display();
      System.out.println("Shortest path is " + b.win());  //5

      b = new Board(4,4,"-WX--W-W-WW-S---");     //Example Board -1
      b.display();
      System.out.println("Shortest path is " + b.win());  //5

      //what other test cases should you test?

   }

期望的输出：

 W-S-
 ----
 --X-
 Shortest path is 2

 S-W
 ---
 --X
 -W-
 Shortest path is 4

 X-WS
 --W-
 W---
 Shortest path is 7

 W--WW
 -X---
 -SWWW
 Shortest path is 1

 -SW
 -W-
 W-X
 Shortest path is -1

 -W-----
 -W-W-WX
 --S----
 W----W-
 W--W---
 Shortest path is 5

 -WX-
 -W-W
 -WW-
 S---
 Shortest path is -1

我的错误输出：

W-S-
----
--X-
Shortest path is -1

S-W
---
--X
-W-
Shortest path is 1

X-WS
--W-
W---
Shortest path is -1

W--WW
-X---
-SWWW
Shortest path is -1

-SW
-W-
W-X
Shortest path is 1

-W-----
-W-W-WX
--S----
W----W-
W--W---
Shortest path is 1

-WX-
-W-W
-WW-
S---
Shortest path is 1

我的新大部分正确输出：

W-S-
----
--X-
0 2
Shortest path is 2

S-W
---
--X
-W-
0 0
Shortest path is 4

X-WS
--W-
W---
0 3
Shortest path is 7

W--WW
-X---
-SWWW
0 0
Shortest path is 1

-SW
-W-
W-X
0 1
Shortest path is -1

-W-----
-W-W-WX
--S----
W----W-
W--W---
0 0
Shortest path is 9

-WX-
-W-W
-WW-
S---
0 0
Shortest path is -1

谁能解释一下我做错了什么（就在我的新输出和所需输出之间）以及我该如何解决？

编辑：谢谢 peter 和 mrB，我已经实施了您的建议并更新了我的代码以适应它！

Answer 1

int right = 1 + check(r-1,c+1);

我强烈怀疑你的意思是：

int right = 1 + check(r,c+1);

Answer 2

您的代码似乎有 2 个问题。

首先，您的 win() 函数中的 while 循环会将您的起始位置留在看板的左上角。

z == 0表示z > 0为假，while循环不会被使用。
您不会递增 x 或 y，所以最好 z 条件失败，否则会出现无限循环。

其次，maxPath 从未被赋值。使其成为 0 并且所有超出范围的结果（我认为是第一个）成为 check(x,y) 的结果，因为它是 1 + 0。 -1 结果都是当棋盘左上角是 'W' 或 'X' 时 check(x,y) returns 0 是相等的至 maxPath

您可能还想将 check(x,y) 设置为一个 int 而不是再次调用它以 return 结果（更大的板可能会占用一些资源）。

总结

更新 while 循环以分别使用 z == 0 和增量 x 和 y。
将 maxPath 设置为一个值，例如9999
更改 win() 中的条件以检查 check(x,y) 的结果是否为 < maxPath（否则您可能不会从 win() 中得到 -1 结果，因为有可能 maxPath 会增加 1 或更多，而 != maxPath 会导致 true）。

使用递归在迷宫中找到最短路径？

Finding the shortest path in a maze using recursion?

java

recursion

maze