java - 如何避免访问二维数组中的无效位置？

Question

我正在研究 Knight's Tour 问题，我正在为它制定一个递归解决方案。https://www.chess.com/terms/knights-tour-chess#:~:text=The%20knight's%20tour%20is%20a,same%20square%20more%20than%20once。

我有一个矩阵[8][8] 和一个名为knightMove(int currentRow, int currentColumn);. 这个方法应该将骑士从当前位置可以做出的所有可能的移动添加到一个数组中。如果可能移​​动的位置值等于 0，则将knightMove(newRow, newColumn)从新位置再次调用。

如果它找到了一个死胡同，那么它将在前一次调用中尝试数组中的下一个可能的移动。如果它用完先前的数组位置，它将尝试在此之前调用的数组中的下一个位置，依此类推。该程序只有在找到问题的正确解决方案时才会结束。

现在是我的问题，我想避免使用这么多的“ifs”来检查骑士移动是否超出桌面。

ArrayList <int[]> moves = new ArrayList<int[]>();
int[] arr = new int[2];
int max=8;
if (currentColumn-2 > 0){
    
    if(currentRow - 1 > 0){
        arr[0] = currentColumn-2;
        arr[1] = currentRow-1;  
        moves.add(arr);
    } 
    
    if(currentRow+1 < max){
        arr[0] = currentColumn-2;
        arr[1] = currentRow+1;
        moves.add(arr);
    }
} 
if (currentRow-2 > 0){
    
    if(currentColumn-1 > 0){                
        arr[0] = currentColumn-1;  
        arr[1] = currentRow-2;
        moves.add(arr);  
    } 
    
    if(currentColumn+1 < max){
        arr[0] = currentColumn+1;
        arr[1] = currentRow-2;
        moves.add(arr);
    }
} 
if (currentColumn+2 > 0){
    
    if(currentRow-1 > 0){
        arr[0] = currentColumn+2;
        arr[1] = currentRow-1;  
        moves.add(arr);
    } 
    
    if(currentRow+1 < max){
        arr[0] = currentColumn+2;
        arr[1] = currentRow+1;
        moves.add(arr);
    }
} 
if (currentRow+2 > 0){
   
    if(currentColumn-1 > 0){
        arr[0] = currentColumn-1;  
        arr[1] = currentRow+2;
        moves.add(arr);
    } 
   
    if(currentRow+1 < max){
        arr[0] = currentColumn+2;
        arr[1] = currentRow+1;
        moves.add(arr);
    }
} 

 for (int[] c : moves){
 // recursive logic...
 }

我对无效职位不感兴趣。如果编译器不能访问这样的无效位置，它就不应该对它们做任何事情，也不会破坏我的代码。专注于那些真正有效的职位。我想做类似下面的事情，只添加数组中有效位置的值（Utopic 解决方案）：

int[] temp = {
    table[currentRow-2][currentColumn-1], 
    table[currentRow-2][currentColumn+1], 
    table[currentRow+1][currentColumn-2], 
    table[currentRow-1][currentColumn-2],  
    table[currentRow+2][currentColumn-1], 
    table[currentRow+2][currentColumn+1], 
    table[currentRow-1][currentColumn+2], 
    table[currentRow+1][currentColumn+2]  
};

我希望帮助找出更好的方法来避免访问矩阵中的无效位置。

标签： javaarraysrecursionmatrixknights-tour

Answer 1

这是我的许多测试运行之一的结果。

Origin row: 3, column: 4
    Move to row: 1, column: 5
    Move to row: 1, column: 3
    Move to row: 2, column: 6
    Move to row: 2, column: 2
    Move to row: 4, column: 6
    Move to row: 4, column: 2
    Move to row: 5, column: 5
    Move to row: 5, column: 3

Origin row: 1, column: 1
    Move to row: 0, column: 3
    Move to row: 2, column: 3
    Move to row: 3, column: 2
    Move to row: 3, column: 0

Origin row: 7, column: 7
    Move to row: 5, column: 8
    Move to row: 5, column: 6
    Move to row: 6, column: 5
    Move to row: 8, column: 5

Origin row: 1, column: 7
    Move to row: 0, column: 5
    Move to row: 2, column: 5
    Move to row: 3, column: 8
    Move to row: 3, column: 6

Origin row: 7, column: 1
    Move to row: 5, column: 2
    Move to row: 5, column: 0
    Move to row: 6, column: 3
    Move to row: 8, column: 3

我做的第一件事是创建一个Coordinate类。这使我可以将索引越界测试放在Coordinate课堂上的一个地方。

该knightMove方法计算出有多少移动是有效的，创建一个坐标数组，并返回有效的移动坐标。

这是完整的、可运行的代码。

public class MoveKnight {

    public static void main(String[] args) {
        MoveKnight mk = new MoveKnight();
        displayOutput(mk, 3, 4);
        displayOutput(mk, 1, 1);
        displayOutput(mk, 7, 7);
        displayOutput(mk, 1, 7);
        displayOutput(mk, 7, 1);
    }

    private static void displayOutput(MoveKnight mk, int row, int column) {
        System.out.println("Origin row: " + row + ", column: " + column);
        Coordinate[] output = mk.knightMove(row, column);
        for (int index = 0; index < output.length; index++) {
            System.out.println("    Move to row: " + output[index].getRow() + 
                    ", column: " + output[index].getColumn());
        }
        System.out.println();
    }

    public Coordinate[] knightMove(int currentRow, int currentColumn) {
        Coordinate[] difference = { new Coordinate(-2, 1), new Coordinate(-2, -1), 
                new Coordinate(-1, 2), new Coordinate(-1, -2), new Coordinate(1, 2), 
                new Coordinate(1, -2), new Coordinate(2, 1), new Coordinate(2, -1) };

        int count = 0;
        for (int index = 0; index < difference.length; index++) {
            Coordinate destination = new Coordinate(currentRow, currentColumn);
            destination.incrementCoordinate(difference[index]);
            if (destination.isValid()) {
                count++;
            }
        }

        Coordinate[] output = new Coordinate[count];
        count = 0;
        for (int index = 0; index < difference.length; index++) {
            Coordinate destination = new Coordinate(currentRow, currentColumn);
            destination.incrementCoordinate(difference[index]);
            if (destination.isValid()) {
                output[count++] = destination;
            }
        }

        return output;
    }

    public class Coordinate {

        private int column, row;

        public Coordinate(int row, int column) {
            setRowColumn(row, column);
        }

        public int getColumn() {
            return column;
        }

        public int getRow() {
            return row;
        }

        public void incrementCoordinate(Coordinate increment) {
            this.row += increment.getRow();
            this.column += increment.getColumn();
        }

        public void setRowColumn(int row, int column) {
            this.row = row;
            this.column = column;
        }

        public boolean isValid() {
            return row >= 0 && row < 8 && column >= 0 && column < 8;
        }

    }

}