用递归法在迷宫中寻找最短路径？

Question

最近，我一直在尝试编写一些递归迷宫代码，它可以返回迷宫中的最短路径。如果迷宫中没有路径，那么代码将返回-1。

例如，对于董事会：

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

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

对于董事会：

 -SW
 -W-
 W-X

输出将是-1

这一切都是通过一个board类实现的，该类接受一个字符串和迷宫的尺寸，一个返回最短路径的检查函数，以及一个返回最短路径的win函数，如果没有路径，则返回-1。然而，当我运行代码时，第一个示例的输出为负1，第二个示例的输出为1。

我的代码：

董事会级别：

  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

有人能解释一下我做错了什么（就在我的新输出和期望的输出之间），以及我如何修复它吗？

编辑：谢谢彼得和mrB，我已经实现了你的建议，并更新了我的代码，以适应！

Answer 1

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

我强烈怀疑你的意思是：

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

Answer 2

你的代码似乎有两个问题。

首先，win（）函数中的while循环将把起始位置留在电路板的左上角。

1. z==0这意味着z

其次，maxPath从未被赋值。使其0和所有超出范围的结果（我认为是第一个）成为检查（x，y）的结果，因为它是10。-1结果都是在板的左上角是'W'或'X'时得到的，在这种情况下检查（X，y）返回0，它等于最大路径

您可能还希望将check（x，y）设置为int，而不是再次调用它以返回结果（更大的电路板可能会占用一些资源）。

总之

1. 更新同时循环以分别使用z==0和增量x和y。
2. 设置maxPath为一个值，例如9999
3. 在win（）中更改条件，以检查check（x， y）的结果是否为