java - 迷宫递归代码完成迷宫但返回错误

Question

如能帮助我找出代码中的错误，我将不胜感激。

我正在为我的 Java 类开发一个递归迷宫项目，但完全卡住了。迷宫结束并显示它成功采取的步骤，但最后返回大量错误。

算法在mazeTraversal函数下。

谢谢。

public class Maze {
   static final int DOWN = 0;
   static final int RIGHT = 1;
   static final int UP = 2;
   static final int LEFT = 3;
   static final int ROW_START = 2;
   static final int COLUMN_START = 0;
   static int move = 0;
   static char maze[][] =
      { { '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#' },
        { '#', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.', '#' },
        { '.', '.', '#', '.', '#', '.', '#', '#', '#', '#', '.', '#' },
        { '#', '#', '#', '.', '#', '.', '.', '.', '.', '#', '.', '#' },
        { '#', '.', '.', '.', '.', '#', '#', '#', '.', '#', '.', '.' },
        { '#', '#', '#', '#', '.', '#', '.', '#', '.', '#', '.', '#' },
        { '#', '.', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#' },
        { '#', '#', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#' },
        { '#', '.', '.', '.', '.', '.', '.', '.', '.', '#', '.', '#' },
        { '#', '#', '#', '#', '#', '#', '.', '#', '#', '#', '.', '#' },
        { '#', '.', '.', '.', '.', '.', '.', '#', '.', '.', '.', '#' },
        { '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#' } };


   // method calls mazeTraversal with correct starting point and direction
   public void traverse() {
      boolean result = mazeTraversal( ROW_START, COLUMN_START );

      if ( !result )
         System.out.println( "Maze has no solution." );
   } // end method traverse

   // traverse maze recursively
   public boolean mazeTraversal( int row, int column ) {
       // TO BE COMPLETE
                maze[row][column] = 'x';
                printMaze();
                if (column > 0 && maze[row][column - 1] == '.')
                {
                    maze[row][column - 1] = 'x';
                    return mazeTraversal(row, column - 1);
                }
                else if (column <= 11 && maze[row][column + 1] == '.')
                {
                    maze[row][column + 1] = 'x';
                    return mazeTraversal(row, column + 1);
                }
                else if (row > 0 && maze[row - 1][column] == '.')
                {
                    maze[row - 1][column] = 'x';
                    return mazeTraversal(row - 1, column);
                }
                else if (row <= 11 && maze[row + 1][column] == '.')
                {
                    maze[row + 1][column] = 'x';
                    return mazeTraversal(row + 1, column);
                }
                else
                {
                    maze[row][column] = 'o';
                    if (column <= 11 && maze[row][column + 1]  == 'x')
                    {
                        maze[row][column + 1] = 'o';
                        return mazeTraversal(row, column + 1);
                    }
                    else if (column > 0 && maze[row][column - 1] == 'x')
                    {
                        maze[row][column - 1] = 'o';
                        return mazeTraversal(row, column - 1);
                    }
                    else if (row <= 11 && maze[row + 1][column] == 'x')
                    {
                        maze[row + 1][column] = 'o';
                        return mazeTraversal(row + 1, column);
                    }
                    else if (row > 0 && maze[row - 1][column] == 'x')
                    {
                        maze[row - 1][column] = 'o';
                        return mazeTraversal(row - 1, column);
                    }
                }           
               return true;
   } // end method mazeTraversal

   // draw maze
   public void printMaze() {

      // for each space in maze
      for ( int row = 0; row < maze.length; row++ )
      {
         for ( int column = 0; column < maze[ row ].length;
            column++ )
         {
            if ( maze[ row ][ column ] == '0' )
               System.out.print( " ." );
            else
               System.out.print( " " + maze[ row ][ column ] );
         }

         System.out.println();
      } // end for

      System.out.println();
   } // end method printMaze
} // end class Maze

这里是错误:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 12

    at Maze.mazeTraversal(Maze.java:61)
    at Maze.mazeTraversal(Maze.java:61)
    at Maze.mazeTraversal(Maze.java:61)
    at Maze.mazeTraversal(Maze.java:51)
    at Maze.mazeTraversal(Maze.java:51)
    at Maze.mazeTraversal(Maze.java:51)
    at Maze.mazeTraversal(Maze.java:51)
    at Maze.mazeTraversal(Maze.java:51)
 # . . . . . . # . . . #
    at Maze.mazeTraversal(Maze.java:56)
    at Maze.mazeTraversal(Maze.java:56)
    at Maze.mazeTraversal(Maze.java:46)
    at Maze.mazeTraversal(Maze.java:46)
 # # # # # # # # # # # #

    at Maze.mazeTraversal(Maze.java:46)
    at Maze.mazeTraversal(Maze.java:56)
    at Maze.mazeTraversal(Maze.java:56)
    at Maze.mazeTraversal(Maze.java:56)
    at Maze.mazeTraversal(Maze.java:56)
    at Maze.mazeTraversal(Maze.java:56)
    at Maze.mazeTraversal(Maze.java:51)
    at Maze.mazeTraversal(Maze.java:51)
    at Maze.mazeTraversal(Maze.java:51)
    at Maze.mazeTraversal(Maze.java:51)
    at Maze.mazeTraversal(Maze.java:69)
    at Maze.mazeTraversal(Maze.java:69)
    at Maze.mazeTraversal(Maze.java:79)
    at Maze.mazeTraversal(Maze.java:79)
    at Maze.mazeTraversal(Maze.java:69)
    at Maze.mazeTraversal(Maze.java:46)
    at Maze.mazeTraversal(Maze.java:56)
    at Maze.mazeTraversal(Maze.java:56)
    at Maze.mazeTraversal(Maze.java:69)
    at Maze.mazeTraversal(Maze.java:46)
    at Maze.mazeTraversal(Maze.java:46)
    at Maze.mazeTraversal(Maze.java:46)
    at Maze.mazeTraversal(Maze.java:61)
    at Maze.mazeTraversal(Maze.java:61)
    at Maze.mazeTraversal(Maze.java:61)
    at Maze.mazeTraversal(Maze.java:61)
    at Maze.mazeTraversal(Maze.java:51)
    at Maze.mazeTraversal(Maze.java:69)
    at Maze.mazeTraversal(Maze.java:69)
    at Maze.mazeTraversal(Maze.java:46)
    at Maze.mazeTraversal(Maze.java:46)
    at Maze.mazeTraversal(Maze.java:61)
    at Maze.mazeTraversal(Maze.java:61)
    at Maze.mazeTraversal(Maze.java:61)
    at Maze.mazeTraversal(Maze.java:51)
    at Maze.mazeTraversal(Maze.java:51)
    at Maze.mazeTraversal(Maze.java:56)
    at Maze.mazeTraversal(Maze.java:51)
    at Maze.traverse(Maze.java:31)
    at MazeTest.main(MazeTest.java:9)
/Users/user/Library/Caches/NetBeans/8.2/executor-snippets/run.xml:53: Java returned: 1

Answer 1

<=下面的(小于或等于)运算符都是不正确的，它们应该只是 < (小于):

else if (column <= 11 && maze[row][column + 1] == '.')
else if (row <= 11 && maze[row + 1][column] == '.')
    if (column <= 11 && maze[row][column + 1]  == 'x')
    else if (row <= 11 && maze[row + 1][column] == 'x')

此外，您需要添加明确的迷宫测试结束(即检查 ROW_END 和 COLUMN_END )，否则上述更改将导致您的代码探索和回溯整个迷宫:

static final int ROW_END = 4;
static final int COLUMN_END = 11;

// ...

// traverse maze recursively
public boolean mazeTraversal(int row, int column)
{
    maze[row][column] = 'x';
    printMaze();

    if (column == COLUMN_END && row == ROW_END)
    {
        return true;
    }

    if (column > 0 && maze[row][column - 1] == '.')
    {
        maze[row][column - 1] = 'x';
        return mazeTraversal(row, column - 1);
    }

    if (column < 11 && maze[row][column + 1] == '.')
    {
        maze[row][column + 1] = 'x';
        return mazeTraversal(row, column + 1);
    }

    if (row > 0 && maze[row - 1][column] == '.')
    {
        maze[row - 1][column] = 'x';
        return mazeTraversal(row - 1, column);
    }

    if (row < 11 && maze[row + 1][column] == '.')
    {
        maze[row + 1][column] = 'x';
        return mazeTraversal(row + 1, column);
    }

    maze[row][column] = 'o';

    if (column < 11 && maze[row][column + 1] == 'x')
    {
        maze[row][column + 1] = 'o';
        return mazeTraversal(row, column + 1);
    }

    if (column > 0 && maze[row][column - 1] == 'x')
    {
        maze[row][column - 1] = 'o';
        return mazeTraversal(row, column - 1);
    }

    if (row < 11 && maze[row + 1][column] == 'x')
    {
        maze[row + 1][column] = 'o';
        return mazeTraversal(row + 1, column);
    }

    if (row > 0 && maze[row - 1][column] == 'x')
    {
        maze[row - 1][column] = 'o';
        return mazeTraversal(row - 1, column);
    }

    return true;
} // end method mazeTraversal