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

问题描述

最近我一直在尝试一些递归迷宫代码，它返回迷宫中的最短路径。如果没有通过迷宫的路径，则代码将返回 -1。

例如，对于董事会：

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

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

对于董事会：

 -SW
 -W-
 W-X

输出将是-1

这一切都是通过一个接收字符串和迷宫尺寸的棋盘类、一个返回最短路径的检查函数和一个返回最短路径的 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

有人可以解释我做错了什么（就在我的新输出和所需输出之间）以及我该如何解决它？

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

标签： javarecursionmaze

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

问题描述

解决方案

推荐阅读