Java递归迷宫求解器问题

我想写一个使用递归的迷宫求解器，它似乎会尝试每个方向一次，然后停下来，我找不出原因。如果您发现问题，请告诉我。关键 0是一个开放的空间 1是一堵墙 2是路径 3的一部分迷宫Java递归迷宫求解器问题

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(); 
    } 
    } 
}

来源

2014-03-07 user3390133

您是否尝试过使用调试器来帮助您弄清楚您的程序可能会做错什么？如果这是我的任务，那就是我开始的地方。 –

看来，它经历了每个方向一次，而十不重复 – user3390133

是的，但为什么？这是因为你的程序逻辑有问题，你必须先确定问题出在哪里。如果没有首先进行调查，你有点过早来到这里。 –

你问这个迷宫递归拼图四个问题在过去的五年结束小时，这证明了它是多么复杂。整个概念1/1迷宫格吸引了我，我想出了一个类应该使它更简单很多。如果你需要做递归，那么它对你没有用处，但是如果你可以使用它，它将消除它的大部分复杂性。

有两个类，一个Enum。

首先，enum定义了您希望在网格中移动的方向，并根据其移动确定一次一个新的索引。

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; 
    } 
};

主类被称为MazePosition（如下）。首先，你设置的迷宫网双阵列进去，通过其int[][]构造函数和静态存储实例：

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

（此步骤可以设计更好，但它的工作原理）

设置完成后迷宫网格（其是一次性唯一，每次执行），则X/Y构造用于声明的初始位置：

MazePosition pos = new MazePosition(0, 0);

在这之后，只要将作为必要的：

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

每个位置的值由pos.getValue()或pos.isPath()检索 - 我认为1是“墙”，0是“路径”。（顺便说一句：巨大的2d阵列应该包含一位booleans，而不是4字节的ints，但看在阵列的代码是合理的int s，并且不与布尔值...注意它至少应该改为byte秒）

所以对于运动，如果你试图得到一个邻居时，有没有，比如向左移动的左边缘处，一个IllegalStateException被抛出。使用is*Edge()函数来避免这种情况。

MazePosition类还有一个方便的调试函数，称为getNineByNine()，它返回数组值为9x9的网格（作为字符串），其中中间项是当前位置。

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]); 
    } 
}

这是什么没有，是“碰撞检测”或任何实际上为你找出迷宫路径。它只是在整个网格中移动，无论它是否穿过墙壁。可以很容易地添加一些getNeighborIfNotWall(Direction)和isWallToLeft()函数，但我会把它留给你。;）

（事实上，这些类没有太多的变化，可以用来遍历任何二维数组，但我可能会添加对角方向，如UP_LEFT，以及移动多个步骤的能力，如getNeighbor(3, Direction.DOWN) ）。

这里的一个示范的使用：

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()); 
    } 

}

输出

[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]

而这里的整个源代码文件，包含上述所有（包括巨型迷宫阵列）的：

//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()); 
    } 

}

来源

2014-03-07 03:56:25 aliteralmind

非常感谢您的洞察力，这个问题真的让我烦恼。：D – user3390133

不客气。祝你好运。 – aliteralmind

http://aliteralmind.wordpress.com/2014/03/07/traverse_2d_array – aliteralmind

看到您已经接受了答案，但无论如何我都会添加该答案...

递归可以解决一些问题，一个非常优雅的方式，但它可以采取一些围绕让你的头。因此，这不是一个确切的答案，为什么你的代码不起作用，而是更高层次的如何在这样的问题中使用递归。

递归问题一般有两个部分数据：一些整体拼图状态，并与当前的尝试相关的一些状态。整个递归事情的作品，因为每次调用递归函数时你推一些新的状态到调用堆栈，当函数退出它是为您删除，让你准备尝试下一个选项。您还可以递归函数内操作的整体拼图状态，但通常当你开始我建议退出当你在你的函数拼图状态的任何改变应被还原。

所以你的情况，迷宫本身是益智的状态，当前的路径是整个拼图状态的临时改变，且当前位置与当前调用堆栈相关的临时状态。

所以整体解决方案开始采取的形式：

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

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

和主要功能只是提供起始坐标：

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

因此，下一步是的“解决”体功能（我已经将迷宫数据中的退出位置设置为3，参见末尾的完整解决方案），其变为：

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; 
    }

这首先检查我们是否在出口处的简单情况，如果情况如此，则返回true。如果没有，我们将当前单元格推到路径上，并查找可用的邻居。如果我们找到一个我们依次尝试，这是递归的核心......如果没有可用的邻居工作，那么我们失败了，并且不得不倒退。

最后，如果我们回溯，我们必须从路径中删除当前单元格。

就是这样。在“可用”功能只检查潜在的细胞是在界限，而不是在墙上或已在当前路径：

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); 
    }

全码：

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(); 
    } 
    } 
}

最后，如果你要打印出来所有可能的解决方案，而不是只找到第一个，然后只是将解决的功能的顶部更改为：

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

快乐递归！

来源

2014-03-07 05:31:45 Barney

这太好了。当我的大脑不被炸时再读一遍。博客文章值得。 – aliteralmind

我把我的答案转贴为一个自我回答的问题，并给出了你的回答。 http://stackoverflow.com/questions/22253140/how-to-freely-traverse-the-elements-in-a-two-dimensional-array-by-cardinal-direc/ – aliteralmind

谢谢 - 很高兴它给了你另一种观点递归。干杯。 – Barney

Java递归迷宫求解器问题

回答

相关问题