Java递归迷宫求解器问题

在过去五个小时中，您已经问过有关此迷宫递归难题的四个问题，这证明它有多复杂。这整个概念的1/0迷宫电网已吸引了我，我想出了一个类，使它成为一个整体
变得简单许多。如果需要进行递归，那么它将对您没有用，但是如果您可以使用它，那么它将消除很多复杂性。

有两个类，一个枚举。

首先，枚举定义您要在网格中移动的方向，并基于其移动一次确定新索引。

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

-我认为

是“墙”并且

是“路径”
来检索。（顺便说一句：巨大的2d数组实际上应该包含一个bit

booleans

，而不是4个字节

ints

，但是使用s来查看
数组的代码是有意义

int

的，而不是使用布尔值。请注意，至少它应该是改为

byte

s。）

因此，关于移动，如果您尝试在没有邻居时找到邻居，例如在左边缘向左移动，

IllegalStateException

则会抛出an
。使用

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", "rn");      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_pre]java MazePosDemostart: [0,0]=1right: [0,1]=1right: [0,2]=1down:  [1,2]=1down:  [2,2]=1right: [2,3]=1down:  [3,3]=0left:  [3,2]=1up:    [2,2]=1up:    [1,2]=1Middle 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", "rn");      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());   }}

Java递归迷宫求解器问题

面试问答相关栏目本月热门文章