如何通过基数方向自由地遍历二维数组中的元素？ （向下，向上，向左，向右）
这个问题是关于通过迷宫计算路径，如二维数组所表示的那样。 例如，通过这个迷宫的路径
0 1 2 3 4 --------- 0| 1 0 1 1 1 1| 1 0 0 0 1 2| 1 0 1 0 1 3| 1 1 1 0 1 4| 1 1 1 0 1 是
START: [0,1] Down: [1,1] Right: [1,2] Right: [1,3] Down: [2,3] Down: [3,3] Down: [4,3]
这张海报试图用递归的方式完成这个，并且实际上在五个小时内发布了四个不同的问题 – 这说明了它的复杂性。
这让我想到了更通用的问题：如何在任何基本方向上自由地在二维数组中移动元素？ 向下，向上，向左，向右
如果这个问题可以解决，那么遍历迷宫就会容易得多。
我用两个类和一个枚举来解决这个问题。
首先，枚举，定义您想要移动的方向，并根据其移动一次一个地确定新索引。
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; } };
主类称为GridPosition （下图）。 首先，通过其int[][]构造函数将双数组网格设置为它，并静态存储该实例：
private static final GridPosition GRID_HOLDER = new GridPosition(GRID);
（这个步骤可以更好地设计，但它可以工作。此外，它应该接受任何类型。）
设置网格（这是一次性的，每次执行）之后，x / y构造函数用于声明初始位置：
GridPosition pos = new GridPosition(0, 0);
然后，根据需要移动：
pos = pos.getNeighbor(Direction.RIGHT); pos = pos.getNeighbor(Direction.RIGHT); pos = pos.getNeighbor(Direction.DOWN); ...
pos.getValue()检索每个位置的值。 （顺便说一句：用于迷宫的巨大的2darrays – 在这篇文章的底部，在“完整代码”中 – 应该真的包含一位booleans ，而不是4字节的ints ，但是看着数组的代码对于int是有意义的，而不是与布尔值有关…请注意，它至少应该更改为byte s。）
因此，关于移动，如果在没有移动时尝试获取邻居，例如在左边缘向左移动，则抛出IllegalStateException 。 使用is*Edge()函数来避免这种情况。
GridPosition类还有一个方便的调试函数getNineByNine() ，它返回数组值的9×9网格（作为字符串），其中中间项是当前位置。
import java.util.Arrays; import java.util.Objects; class GridPosition { //state private static int[][] GRID; private final int rowIdx; private final int colIdx; //internal private final int rowIdxMinus1; private final int colIdxMinus1; public GridPosition(int[][] GRID) { if(this.GRID != null) { throw new IllegalStateException("Grid already set. Use x/y constructor."); } GridPosition.GRID = 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 GridPosition(int rowIdx, int colIdx) { if(GridPosition.GRID == null) { throw new IllegalStateException("Must set grid with: new GridPosition(int[][])."); } if(rowIdx < 0 || rowIdx >= GridPosition.getRowCount()) { throw new IllegalArgumentException("rowIdx (" + rowIdx + ") is invalid."); } if(colIdx < 0 || colIdx >= GridPosition.getColumnCount()) { throw new IllegalArgumentException("colIdx (" + colIdx + ") is invalid."); } this.rowIdx = rowIdx; this.colIdx = colIdx; rowIdxMinus1 = (rowIdx - 1); colIdxMinus1 = (colIdx - 1); } public int getValue() { return GridPosition.GRID[getRowIdx()][getColumnIdx()]; } public int getRowIdx() { return rowIdx; } public int getColumnIdx() { return colIdx; } public GridPosition getNeighbor(Direction dir) { Objects.requireNonNull(dir, "dir"); return (new GridPosition( dir.getNewRowIdx(getRowIdx()), dir.getNewColIdx(getColumnIdx()))); } public GridPosition getNeighborNullIfEdge(Direction dir) { if(isEdgeForDirection(dir)) { return null; } return getNeighbor(dir); } public int getNeighborValueNeg1IfEdge(Direction dir) { GridPosition pos = getNeighborNullIfEdge(dir); return ((pos == null) ? -1 : pos.getValue()); } public static final int getRowCount() { return GRID.length; } public static final int getColumnCount() { return 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 GridPosition 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 GridPosition 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 GridPosDemo { private static final int[][] GRID = new int[][] { //mega grid goes here... }; private static final GridPosition GRID_HOLDER = new GridPosition(GRID); public static final void main(String[] ignored) { GridPosition pos = new GridPosition(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 GridPosDemo 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]
为了使用它来穿越迷宫中的正确路径，这需要添加“碰撞检测”（因此它不会穿过墙壁），此外还要跟踪你去过的地方（所以你不要回到起始位置）。 比如用一些getNeighborIfNotWall(Direction)和isWallToLeft()函数。
抛开迷宫问题，在考虑完成这些课程之前，我会做以下几点：
- 使数组类型通用，而不是整数
- 添加错误检查，如代码中所述
- 重新设计网格的设置方式。
- 添加对角线方向：
UP_LEFT，UP_RIGHT，DOWN_LEFT，DOWN_RIGHT - 添加在一个方向上移动多个步骤的function：
getNeighbor(3, Direction.DOWN)
这是整个源代码文件，包含以上所有内容（包括巨型迷宫网格）：
//Needed only by GridPosition 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 GridPosition { //config private static int[][] GRID; private final int rowIdx; private final int colIdx; //internal private final int rowIdxMinus1; private final int colIdxMinus1; public GridPosition(int[][] GRID) { if(this.GRID != null) { throw new IllegalStateException("Grid already set. Use x/y constructor."); } GridPosition.GRID = 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 GridPosition(int rowIdx, int colIdx) { if(GridPosition.GRID == null) { throw new IllegalStateException("Must set grid with: new GridPosition(int[][])."); } if(rowIdx < 0 || rowIdx >= GridPosition.getRowCount()) { throw new IllegalArgumentException("rowIdx (" + rowIdx + ") is invalid."); } if(colIdx < 0 || colIdx >= GridPosition.getColumnCount()) { throw new IllegalArgumentException("colIdx (" + colIdx + ") is invalid."); } this.rowIdx = rowIdx; this.colIdx = colIdx; rowIdxMinus1 = (rowIdx - 1); colIdxMinus1 = (colIdx - 1); } public int getValue() { return GridPosition.GRID[getRowIdx()][getColumnIdx()]; } public int getRowIdx() { return rowIdx; } public int getColumnIdx() { return colIdx; } public GridPosition getNeighbor(Direction dir) { Objects.requireNonNull(dir, "dir"); return (new GridPosition( dir.getNewRowIdx(getRowIdx()), dir.getNewColIdx(getColumnIdx()))); } public GridPosition getNeighborNullIfEdge(Direction dir) { if(isEdgeForDirection(dir)) { return null; } return getNeighbor(dir); } public int getNeighborValueNeg1IfEdge(Direction dir) { GridPosition pos = getNeighborNullIfEdge(dir); return ((pos == null) ? -1 : pos.getValue()); } public static final int getRowCount() { return GRID.length; } public static final int getColumnCount() { return 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 GridPosition 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 GridPosition 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 GridPosDemo { private static final int[][] 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 GridPosition GRID_HOLDER = new GridPosition(GRID); public static final void main(String[] ignored) { GridPosition pos = new GridPosition(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()); } }