Java Recursive Maze Solver problems

2019-01-12 01:40发布

站内问答 / Java
793 2 2

I am trying to write a maze solver using recursion, and it seems that it tries each direction once, then stops and I can't figure out why. If you see a problem, please let me know. Key 0 is an open space 1 is a wall 2 is part of the path 3 is the end of the maze

public class Maze{
  public static void main(String[] args){
    int[][] maze = 
     {{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
      {0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1},
      {1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1},
      {1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,1},
      {1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1},
      {1,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1},
      {1,0,1,1,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1},
      {1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,1},
      {1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1},
      {1,0,1,0,1,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,1},
      {1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,1,1},
      {1,0,1,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1},
      {1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1},
      {1,0,1,0,1,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1},
      {1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1},
      {1,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,1},
      {1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1},
      {1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,1},
      {1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1},
      {1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1},
      {1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1},
      {1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,1,0,1},
      {1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1},
      {1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1},
      {1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1},
      {1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,1},
      {1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,0,1},
      {1,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,0,0,1,0,1,0,1},
      {1,0,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,1,1,1,1,0,1},
      {1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,1},
      {1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1},
      {1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1},
      {1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1},
      {1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1},
      {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1}};
    boolean[][] posCheck = new boolean[maze.length][maze[0].length];
    int r = 0;
    int c = 0;
    for(int row = 0; row < maze.length; row++){
      for(int col = 0; col < maze[row].length; col++){
        if(maze[row][col]==0){
          r = row;
          c = col;
        }
      }
    }
    maze[r][c] = 3;
    mazeSolver(1, 0, 0, maze, posCheck);
  }

  public static boolean mazeSolver(int r, int c, int d, int[][]maze, boolean[][] posCheck){
    maze[r][c] = 2;

    if(maze[r][c] == 3){
      print(maze);
      return true;
    }

    if((c+1 < maze.length) && maze[r][c+1]==0 && d != 1 && !posCheck[r][c+1]){
      if(d != 3)
        posCheck[r][c+1] = true;
      if(mazeSolver(r, c + 1, 3, maze, posCheck)){
        maze[r][c] = 2;
        return true;
      }
    }

    if((r-1 >= 0) && maze[r-1][c]==0 && !posCheck[r-1][c] && d != 2){
      if(d != 4)
        posCheck[r-1][c] = true;
      if(mazeSolver(r - 1, c, 4, maze, posCheck)){
        maze[r][c] = 2;
        return true;
      }
    }

    if((c-1 >= 0) && maze[r][c-1]==0 && !posCheck[r][c-1] && d != 3){
      if(d != 1)
        posCheck[r][c-1] = true;
      if(mazeSolver(r, c - 1, 1, maze, posCheck)){
        maze[r][c] = 2;
        return true;
      }
    }

    if((r+1 < maze.length) && maze[r+1][c]==0 && !posCheck[r+1][c] && d != 4){
      if(d != 2)
        posCheck[r+1][c] = true;
      if(mazeSolver(r + 1, c, 4, maze, posCheck)){
        maze[r][c] = 2;
        return true;
      }
    }

    print(maze);
    return false;
  }

  public static void print(int[][] maze){
    for(int row = 0; row<maze.length; row++){
      for(int col = 0; col<maze[row].length; col++)
        System.out.print(maze[row][col]);
      System.out.println();
    }
  }
}

2条回答
萌系小妹纸
2楼-- · 2019-01-12 02:12

You have asked four questions about this maze-recursion puzzle in the past five hours, which attests to how complicated it is. This whole concept a 1/0 maze-grid has intrigued me, and I've come up with a class that should make it a whole lot simpler. If you're required to do recursion, then it will not be useful to you, but if you can use it, it eliminates much of its complexity.

There are two classes, and an Enum.

First, the enum, which defines the direction you want to move in the grid and determines the new indexes, one-at-a-time, based on its movement.

enum Direction {
   UP(-1, 0),
   DOWN(1, 0),
   LEFT(0, -1),
   RIGHT(0, 1);

   private final int rowSteps;
   private final int colSteps;
   private Direction(int rowSteps, int colSteps)  {
      this.rowSteps = rowSteps;
      this.colSteps = colSteps;
   }
   public int getNewRowIdx(int currentRowIdx)  {
      return  (currentRowIdx + getRowSteps());
   }
   public int getNewColIdx(int currentColIdx)  {
      return  (currentColIdx + getColSteps());
   }
   public int getRowSteps()  {
      return  rowSteps;
   }
   public int getColSteps()  {
      return  colSteps;
   }
};

The main class is called MazePosition (below). First you set the maze-grid double-array into it, via its int[][] constructor, and store that instance statically:

private static final MazePosition MAZE_HOLDER = new MazePosition(MAZE_GRID);

(This step could be designed better, but it works.)

After setting the maze-grid (which is a one-time-only thing, per-execution), then the x/y constructor is used to declare an initial position:

MazePosition pos = new MazePosition(0, 0);

And after that, just move as necessary:

pos = pos.getNeighbor(Direction.RIGHT);
pos = pos.getNeighbor(Direction.RIGHT);
pos = pos.getNeighbor(Direction.DOWN);
...

The value of each position is retrieved by pos.getValue() or pos.isPath()--I think 1 is a "wall" and 0 is the "path". (As an aside: The huge 2d-array should really contain one-bit booleans, instead of 4-byte ints, but looking at the array's code makes sense with ints, and doesn't with booleans... Note that it should at least be changed to bytes.)

So regarding movement, if you attempt to get a neighbor when there is none, such as moving left at the left edge, an IllegalStateException is thrown. Use the is*Edge() functions to avoid this.

The MazePosition class also has a convenient debugging function called getNineByNine(), which returns a 9x9 grid of the array values (as a string), where the middle item is the current position.

   import  java.util.Arrays;
   import  java.util.Objects;
class MazePosition  {
//state
   private static int[][] MAZE_GRID;
   private final int rowIdx;
   private final int colIdx;
//internal
   private final int rowIdxMinus1;
   private final int colIdxMinus1;
   public MazePosition(int[][] MAZE_GRID)  {
      if(this.MAZE_GRID != null)  {
         throw  new IllegalStateException("Maze double-array already set. Use x/y constructor.");
      }
      MazePosition.MAZE_GRID = MAZE_GRID;

      //TODO: Crash if null or empty, or sub-arrays null or empty, or unequal lengths, or contain anything but 0 or -1.

      rowIdx = -1;
      colIdx = -1;
      rowIdxMinus1 = -1;
      colIdxMinus1 = -1;
   }
   public MazePosition(int rowIdx, int colIdx)  {
      if(MazePosition.MAZE_GRID == null)  {
         throw  new IllegalStateException("Must set maze double-array with: new MazePosition(int[][]).");
      }

      if(rowIdx < 0  ||  rowIdx >= MazePosition.getRowCount())  {
         throw  new IllegalArgumentException("rowIdx (" + rowIdx + ") is invalid.");
      }
      if(colIdx < 0  ||  colIdx >= MazePosition.getColumnCount())  {
         throw  new IllegalArgumentException("colIdx (" + colIdx + ") is invalid.");
      }

      this.rowIdx = rowIdx;
      this.colIdx = colIdx;
      rowIdxMinus1 = (rowIdx - 1);
      colIdxMinus1 = (colIdx - 1);
   }

   public boolean isPath()  {  
      return  (getValue() == 0);  //1???
   }
   public int getValue()  {
      return  MazePosition.MAZE_GRID[getRowIdx()][getColumnIdx()];
   }
   public int getRowIdx()  {
      return  rowIdx;
   }
   public int getColumnIdx()  {
      return  colIdx;
   }
   public MazePosition getNeighbor(Direction dir)  {
      Objects.requireNonNull(dir, "dir");
      return  (new MazePosition(
         dir.getNewRowIdx(getRowIdx()), 
         dir.getNewColIdx(getColumnIdx())));
   }
   public MazePosition getNeighborNullIfEdge(Direction dir)  {
      if(isEdgeForDirection(dir))  {
         return  null;
      }
      return  getNeighbor(dir);
   }
   public int getNeighborValueNeg1IfEdge(Direction dir)  {
      MazePosition pos = getNeighborNullIfEdge(dir);
      return  ((pos == null) ? -1 : pos.getValue());
   }
   public static final int getRowCount()  {
      return  MAZE_GRID.length;
   }
   public static final int getColumnCount()  {
      return  MAZE_GRID[0].length;
   }
   public boolean isEdgeForDirection(Direction dir)  {
      Objects.requireNonNull(dir);
      switch(dir)  {
         case UP:    return isTopEdge(); 
         case DOWN:  return isBottomEdge(); 
         case LEFT:  return isLeftEdge();
         case RIGHT: return isRightEdge(); 
      }
      throw  new IllegalStateException(toString() + ", dir=" + dir);
   }
   public boolean isLeftEdge()  {
      return  (getColumnIdx() == 0);
   }
   public boolean isTopEdge()  {
      return  (getRowIdx() == 0);
   }
   public boolean isBottomEdge()  {
      return  (getRowIdx() == rowIdxMinus1);
   }
   public boolean isRightEdge()  {
      return  (getColumnIdx() == colIdxMinus1);
   }
   public String toString()  {
      return  "[" + getRowIdx() + "," + getColumnIdx() + "]=" + getValue();
   }
   public String getNineByNine()  {
      int[][] nineByNine = new int[3][3];

      //Middle row
         nineByNine[1][1] = getValue();
         nineByNine[1][0] = getNeighborValueNeg1IfEdge(Direction.LEFT);
         nineByNine[1][2] = getNeighborValueNeg1IfEdge(Direction.RIGHT);

      //Top
         MazePosition posUp = getNeighborNullIfEdge(Direction.UP);
         if(posUp != null)  {
            nineByNine[0][0] = posUp.getNeighborValueNeg1IfEdge(Direction.LEFT);
            nineByNine[0][1] = posUp.getValue();
            nineByNine[0][2] = posUp.getNeighborValueNeg1IfEdge(Direction.RIGHT);
         }

      //Bottom
         MazePosition posDown = getNeighborNullIfEdge(Direction.DOWN);
         if(posDown != null)  {
            nineByNine[2][0] = posDown.getNeighborValueNeg1IfEdge(Direction.LEFT);
            nineByNine[2][1] = posDown.getValue();
            nineByNine[2][2] = posDown.getNeighborValueNeg1IfEdge(Direction.RIGHT);
         }

      String sLS = System.getProperty("line.separator", "\r\n");
      return  "Middle position in 9x9 grid is *this*: " + toString() + sLS + 
         Arrays.toString(nineByNine[0]) + sLS + 
         Arrays.toString(nineByNine[1]) + sLS + 
         Arrays.toString(nineByNine[2]);
   }
}

What this does not have, is "collision detection" or anything that actually figures out the maze-path for you. It just moves throughout the grid, regardless if it's moving through walls or not. There could easily be some getNeighborIfNotWall(Direction) and isWallToLeft() functions added, but I'll leave that to you. ;)

(Actually, these classes, without too much change, could be used to traverse any 2D array, although I'd probably add diagonal directions, such as UP_LEFT, and the ability to move multiple steps, such as getNeighbor(3, Direction.DOWN)).

Here's a demo usage:

public class MazePosDemo  {
   private static final int[][] MAZE_GRID = new int[][] {

   //mega maze grid goes here...

   };

   private static final MazePosition MAZE_HOLDER = new MazePosition(MAZE_GRID);

   public static final void main(String[] ignored)  {
      MazePosition pos = new MazePosition(0, 0);
      System.out.println("start: " + pos);

      pos = pos.getNeighbor(Direction.RIGHT);
      System.out.println("right: " + pos);

      pos = pos.getNeighbor(Direction.RIGHT);
      System.out.println("right: " + pos);

      pos = pos.getNeighbor(Direction.DOWN);
      System.out.println("down:  " + pos);

      pos = pos.getNeighbor(Direction.DOWN);
      System.out.println("down:  " + pos);

      pos = pos.getNeighbor(Direction.RIGHT);
      System.out.println("right: " + pos);

      pos = pos.getNeighbor(Direction.DOWN);
      System.out.println("down:  " + pos);

      pos = pos.getNeighbor(Direction.LEFT);
      System.out.println("left:  " + pos);

      pos = pos.getNeighbor(Direction.UP);
      System.out.println("up:    " + pos);

      pos = pos.getNeighbor(Direction.UP);
      System.out.println("up:    " + pos);

      System.out.println(pos.getNineByNine());
   }

}

Output

[C:\java_code\]java MazePosDemo
start: [0,0]=1
right: [0,1]=1
right: [0,2]=1
down:  [1,2]=1
down:  [2,2]=1
right: [2,3]=1
down:  [3,3]=0
left:  [3,2]=1
up:    [2,2]=1
up:    [1,2]=1
Middle position in 9x9 grid is *this*: [1,2]=1
[1, 1, 1]
[0, 1, 0]
[0, 1, 1]

And here's the entire source-code file, containing all of the above (including the mega-maze-array):

   //Needed only by MazePosition
   import  java.util.Arrays;
   import  java.util.Objects;

enum Direction {
   UP(-1, 0),
   DOWN(1, 0),
   LEFT(0, -1),
   RIGHT(0, 1);
//config
   private final int rowSteps;
   private final int colSteps;
   private Direction(int rowSteps, int colSteps)  {
      this.rowSteps = rowSteps;
      this.colSteps = colSteps;
   }
   public int getNewRowIdx(int currentRowIdx)  {
      return  (currentRowIdx + getRowSteps());
   }
   public int getNewColIdx(int currentColIdx)  {
      return  (currentColIdx + getColSteps());
   }
   public int getRowSteps()  {
      return  rowSteps;
   }
   public int getColSteps()  {
      return  colSteps;
   }
};

class MazePosition  {
//config
   private static int[][] MAZE_GRID;
   private final int rowIdx;
   private final int colIdx;
//internal
   private final int rowIdxMinus1;
   private final int colIdxMinus1;
   public MazePosition(int[][] MAZE_GRID)  {
      if(this.MAZE_GRID != null)  {
         throw  new IllegalStateException("Maze double-array already set. Use x/y constructor.");
      }
      MazePosition.MAZE_GRID = MAZE_GRID;

      //TODO: Crash if null or empty, or sub-arrays null or empty, or unequal lengths, or contain anything but 0 or -1.

      rowIdx = -1;
      colIdx = -1;
      rowIdxMinus1 = -1;
      colIdxMinus1 = -1;
   }
   public MazePosition(int rowIdx, int colIdx)  {
      if(MazePosition.MAZE_GRID == null)  {
         throw  new IllegalStateException("Must set maze double-array with: new MazePosition(int[][]).");
      }

      if(rowIdx < 0  ||  rowIdx >= MazePosition.getRowCount())  {
         throw  new IllegalArgumentException("rowIdx (" + rowIdx + ") is invalid.");
      }
      if(colIdx < 0  ||  colIdx >= MazePosition.getColumnCount())  {
         throw  new IllegalArgumentException("colIdx (" + colIdx + ") is invalid.");
      }

      this.rowIdx = rowIdx;
      this.colIdx = colIdx;
      rowIdxMinus1 = (rowIdx - 1);
      colIdxMinus1 = (colIdx - 1);
   }

   public boolean isPath()  {  
      return  (getValue() == 0);  //1???
   }
   public int getValue()  {
      return  MazePosition.MAZE_GRID[getRowIdx()][getColumnIdx()];
   }
   public int getRowIdx()  {
      return  rowIdx;
   }
   public int getColumnIdx()  {
      return  colIdx;
   }
   public MazePosition getNeighbor(Direction dir)  {
      Objects.requireNonNull(dir, "dir");
      return  (new MazePosition(
         dir.getNewRowIdx(getRowIdx()), 
         dir.getNewColIdx(getColumnIdx())));
   }
   public MazePosition getNeighborNullIfEdge(Direction dir)  {
      if(isEdgeForDirection(dir))  {
         return  null;
      }
      return  getNeighbor(dir);
   }
   public int getNeighborValueNeg1IfEdge(Direction dir)  {
      MazePosition pos = getNeighborNullIfEdge(dir);
      return  ((pos == null) ? -1 : pos.getValue());
   }
   public static final int getRowCount()  {
      return  MAZE_GRID.length;
   }
   public static final int getColumnCount()  {
      return  MAZE_GRID[0].length;
   }
   public boolean isEdgeForDirection(Direction dir)  {
      Objects.requireNonNull(dir);
      switch(dir)  {
         case UP:    return isTopEdge(); 
         case DOWN:  return isBottomEdge(); 
         case LEFT:  return isLeftEdge();
         case RIGHT: return isRightEdge(); 
      }
      throw  new IllegalStateException(toString() + ", dir=" + dir);
   }
   public boolean isLeftEdge()  {
      return  (getColumnIdx() == 0);
   }
   public boolean isTopEdge()  {
      return  (getRowIdx() == 0);
   }
   public boolean isBottomEdge()  {
      return  (getRowIdx() == rowIdxMinus1);
   }
   public boolean isRightEdge()  {
      return  (getColumnIdx() == colIdxMinus1);
   }
   public String toString()  {
      return  "[" + getRowIdx() + "," + getColumnIdx() + "]=" + getValue();
   }
   public String getNineByNine()  {
      int[][] nineByNine = new int[3][3];

      //Middle row
         nineByNine[1][1] = getValue();
         nineByNine[1][0] = getNeighborValueNeg1IfEdge(Direction.LEFT);
         nineByNine[1][2] = getNeighborValueNeg1IfEdge(Direction.RIGHT);

      //Top
         MazePosition posUp = getNeighborNullIfEdge(Direction.UP);
         if(posUp != null)  {
            nineByNine[0][0] = posUp.getNeighborValueNeg1IfEdge(Direction.LEFT);
            nineByNine[0][1] = posUp.getValue();
            nineByNine[0][2] = posUp.getNeighborValueNeg1IfEdge(Direction.RIGHT);
         }

      //Bottom
         MazePosition posDown = getNeighborNullIfEdge(Direction.DOWN);
         if(posDown != null)  {
            nineByNine[2][0] = posDown.getNeighborValueNeg1IfEdge(Direction.LEFT);
            nineByNine[2][1] = posDown.getValue();
            nineByNine[2][2] = posDown.getNeighborValueNeg1IfEdge(Direction.RIGHT);
         }

      String sLS = System.getProperty("line.separator", "\r\n");
      return  "Middle position in 9x9 grid is *this*: " + toString() + sLS + 
         Arrays.toString(nineByNine[0]) + sLS + 
         Arrays.toString(nineByNine[1]) + sLS + 
         Arrays.toString(nineByNine[2]);
   }
}
public class MazePosDemo  {
   private static final int[][] MAZE_GRID = new int[][] {
      {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
      {0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1},
      {1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1},
      {1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,1},
      {1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1},
      {1,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1},
      {1,0,1,1,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1},
      {1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,1},
      {1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1},
      {1,0,1,0,1,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,1},
      {1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,1,1},
      {1,0,1,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1},
      {1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1},
      {1,0,1,0,1,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1},
      {1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1},
      {1,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,1},
      {1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1},
      {1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,1},
      {1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1},
      {1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1},
      {1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1},
      {1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,1,0,1},
      {1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1},
      {1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1},
      {1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1},
      {1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,1},
      {1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,0,1},
      {1,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,0,0,1,0,1,0,1},
      {1,0,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,1,1,1,1,0,1},
      {1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,1},
      {1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1},
      {1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1},
      {1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1},
      {1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1},
      {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1}};
   private static final MazePosition MAZE_HOLDER = new MazePosition(MAZE_GRID);

   public static final void main(String[] ignored)  {
      MazePosition pos = new MazePosition(0, 0);
      System.out.println("start: " + pos);

      pos = pos.getNeighbor(Direction.RIGHT);
      System.out.println("right: " + pos);

      pos = pos.getNeighbor(Direction.RIGHT);
      System.out.println("right: " + pos);

      pos = pos.getNeighbor(Direction.DOWN);
      System.out.println("down:  " + pos);

      pos = pos.getNeighbor(Direction.DOWN);
      System.out.println("down:  " + pos);

      pos = pos.getNeighbor(Direction.RIGHT);
      System.out.println("right: " + pos);

      pos = pos.getNeighbor(Direction.DOWN);
      System.out.println("down:  " + pos);

      pos = pos.getNeighbor(Direction.LEFT);
      System.out.println("left:  " + pos);

      pos = pos.getNeighbor(Direction.UP);
      System.out.println("up:    " + pos);

      pos = pos.getNeighbor(Direction.UP);
      System.out.println("up:    " + pos);

      System.out.println(pos.getNineByNine());
   }

}
查看更多
0人赞 添加讨论(0) 举报
萌系小妹纸
3楼-- · 2019-01-12 02:12

See you've already accepted an answer, but I'll add this in anyway...

Recursion can be a really elegant way to solve some problems, but it can take a bit to get your head around. So this is not an exact answer to why your code doesn't work, but more of a higher level of how to use recursion in problems like this.

Recursion problems generally have two parts to the data: some overall puzzle state, and some state associated with the current attempt. The whole recursion thing works because each time you call the recursive function you push some new state onto the call stack, and when the function exits it is removed for you, leaving you ready to try the next option. You can also manipulate the overall puzzle state within the recursive function, but generally when you're starting I'd suggest that any changes you make to the puzzle state in your function should be reverted when it exits.

So in your case, the maze itself is puzzle state, the current path is a temporary change to the overall puzzle state, and the current position is transient state associated with the current call stack.

So the overall solution starts to take the form:

  // global state
  private static int[][] maze;

  private static boolean solve(int r, int c) {
    // return true if I'm at the exit, false otherwise
  }

and the main function simply provides the starting coords:

  public static void main(String[] args) {
    if (solve(1, 0)) {
      print();
    } else {
      System.out.println("no solution found");
    }
  }

So the next step is the body of the "solve" function (I've set the exit position to 3 in the maze data - see the full solution at the end), which becomes:

  private static boolean solve(int r, int c) {

    if (maze[r][c] == 3) {
      // we've found the exit
      return true;
    }

    // push the current position onto the path
    maze[r][c] == 2;

    // try up / down / left / right - if any of these return true then we're done
    if (available(r - 1, c) && solve(r - 1, c)) {
      return true;
    }
    if (available(r + 1, c) && solve(r + 1, c)) {
      return true;
    }
    if (available(r, c - 1) && solve(r, c - 1)) {
      return true;
    }
    if (available(r, c + 1) && solve(r, c + 1)) {
      return true;
    }

    // no result found from the current position so return false
    // ... but have to revert the temporary state before doing so
    maze[r][c] = 0;

    return false;
  }

This first checks the simple case of if we're at the exit, and returns true if that is the case. If not, we push the current cell on to the path, and look for an available neighbour. If we find one we try each in turn, and this is the core of the recursion... If none of the available neighbours work then we've failed, and have to backtrack.

Finally, if we're backtracking, we have to remove the current cell from the path.

And that's about it. The 'available' function simply checks if the potential cell is in bounds and not a wall or already on the current path:

  private static boolean available(int r, int c) {
    return r >= 0 && r < maze.length
        && c >= 0 && c < maze[r].length
        && (maze[r][c] == 0 || maze[r][c] == 3);
  }

Full code:

public class Maze2 {

  private static int[][] maze = 
     {{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
      {0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1},
      {1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1},
      {1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,1},
      {1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1},
      {1,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1},
      {1,0,1,1,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1},
      {1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,1},
      {1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1},
      {1,0,1,0,1,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,1},
      {1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,1,1},
      {1,0,1,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1},
      {1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1},
      {1,0,1,0,1,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1},
      {1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1},
      {1,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,1},
      {1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1},
      {1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,1},
      {1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1},
      {1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1},
      {1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1},
      {1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,1,0,1},
      {1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1},
      {1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1},
      {1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1},
      {1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,1},
      {1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,0,1},
      {1,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,0,0,1,0,1,0,1},
      {1,0,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,1,1,1,1,0,1},
      {1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,1},
      {1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1},
      {1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1},
      {1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1},
      {1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1},
      {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,3,1}};

  public static void main(String[] args) {
    if (solve(1, 0)) {
      print();
    } else {
      System.out.println("no solution found");
    }
  }

  private static boolean solve(int r, int c) {

    // if we're at the goal then we've solved it
    if (maze[r][c] == 3) {
      return true;
    }

    // mark the current cell as on the path
    maze[r][c] = 2;

    // try all available neighbours - if any of these return true then we're solved
    if (available(r - 1, c) && solve(r - 1, c)) {
      return true;
    }
    if (available(r + 1, c) && solve(r + 1, c)) {
      return true;
    }
    if (available(r, c - 1) && solve(r, c - 1)) {
      return true;
    }
    if (available(r, c + 1) && solve(r, c + 1)) {
      return true;
    }

    // nothing found so remove the current cell from the path and backtrack
    maze[r][c] = 0;

    return false;
  }

  // cell is available if it is in the maze and either a clear space or the
  // goal - it is not available if it is a wall or already on the current path
  private static boolean available(int r, int c) {
    return r >= 0 && r < maze.length
        && c >= 0 && c < maze[r].length
        && (maze[r][c] == 0 || maze[r][c] == 3);
  }

  // use symbols to make reading the output easier...
  private static final char[] SYMBOLS = {' ', '#', '.', '*' };

  private static void print(){
    for(int row = 0; row < maze.length; ++row) {
      for(int col = 0; col < maze[row].length; ++col) {
        System.out.print(SYMBOLS[maze[row][col]]);
      }
      System.out.println();
    }
  }
}

Finally, if you want to print out all possible solutions instead of just the first one found, then just change the top of the solved function to:

// if we're at the goal then print it but return false to continue searching
if (maze[r][c] == 3) {
  print();
  return false;
}

Happy recursing!!!

查看更多
0人赞 添加讨论(0) 举报
登录 后发表回答
相关问题
查看全部
相关文章
查看全部
收藏的人(2)