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遞歸迷宮求解器問題

回答

相關問題