如何避免访问一个无效的位置在二维数组?

Question

我正在研究骑士之旅问题，我正在为它做一个递归解决方案。https://www.chess.com/terms/knights-tour-chess: ~:文本= % 20骑士的% 20旅游% 20是% 20,相同的% 20平方% 20 % 20多% 20次。

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

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

现在是我的问题，我想避免使用这么多的"如果"来检查一个骑士的移动是否出桌。

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...
}

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

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]  
};

我需要帮助找出一个更好的方法来避免访问矩阵中的无效位置。

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;
}
}
}