Java递归迷宫求解器问题
我正在尝试使用递归编写一个迷宫求解器，它似乎尝试每个方向一次，然后停止，我无法弄清楚为什么。 如果您发现问题，请告诉我。 键0是开放空间1是墙2是路径3的一部分是迷宫的末端
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 = 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(); } } } 在过去的五个小时里，你已经问了四个关于这个迷宫递归谜题的问题，这certificate了它有多复杂。 整个概念1/0迷宫网格引起了我的兴趣，我想出了一个应该让它变得简单得多的课程。 如果您需要进行递归，那么它对您没有用，但如果您可以使用它，它会消除它的大部分复杂性。
有两个类，一个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是有意义的，而不是用布尔值…注意它应该至少要改为byte s。）
因此，关于移动，如果在没有移动时尝试获取邻居，例如在左边缘向左移动，则抛出IllegalStateException 。 使用is*Edge()函数来避免这种情况。
MazePosition类还有一个方便的调试函数getNineByNine() ，它返回数组值的9×9网格（作为字符串），其中中间项是当前位置。
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()函数，但我会留给你。 ;）
（实际上，这些类没有太多变化，可以用来遍历任何2D数组，虽然我可能会添加对角线方向，例如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]
这里是整个源代码文件，包含以上所有内容（包括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()); } }
看到你已经接受了答案，但无论如何我都会添加它…
递归可以是解决某些问题的一种非常优雅的方法，但它可能需要一些时间才能解决问题。 所以这不是一个确切的答案，为什么你的代码不起作用，但更多的是如何在这样的问题中使用递归的更高级别。
递归问题通常包含数据的两个部分：一些整体拼图状态，以及与当前尝试相关的一些状态。 整个递归的工作原理是因为每次调用递归函数时都会将一些新状态推送到调用堆栈，当函数退出时，它会被移除，让您准备好尝试下一个选项。 您还可以在递归函数中操纵整体拼图状态，但通常在您开始时我建议您在函数中对拼图状态所做的任何更改都应在退出时恢复。
因此，在您的情况下，迷宫本身是拼图状态，当前路径是整个拼图状态的临时变化，并且当前位置是与当前调用堆栈相关联的瞬态。
所以整体解决方案开始采取以下forms：
// global state private static int[][] maze; private static boolean solve(int r, int c) { // return true if I'm at the exit, false otherwise }
主要function只是提供起始坐标：
public static void main(String[] args) { if (solve(1, 0)) { print(); } else { System.out.println("no solution found"); } }
所以下一步是“解决”function的主体（我在迷宫数据中将退出位置设置为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。 如果没有，我们将当前单元格推送到路径，并查找可用的邻居。 如果我们找到一个，我们依次尝试每个，这是递归的核心…如果没有可用的邻居工作，那么我们失败了，并且必须回溯。
最后，如果我们回溯，我们必须从路径中删除当前单元格。
这就是它。 ‘available’函数只是检查潜在的单元是否在边界而不是墙或已经在当前路径上：
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; }
快乐的递归!!!