java - 骑士之旅 - java 回溯，出界

Question

这个问题已经有答案了:

What causes a java.lang.ArrayIndexOutOfBoundsException and how do I prevent it? (25 个回答)

已关闭 5 年前。

我正在尝试解决这个问题，该问题指出，给定一个 N * M 棋盘，骑士之旅被定义为骑士的移动序列，使得骑士仅访问每个方格一次。下面是我的代码，但是我得到了 Array out ofbound = 8，我知道当 Moves 尝试在当前行中添加值 2 和 6 时就会出现这种情况，但我不知道如何摆脱它。

int MaxMove = 64; // for 8*8 chess Board
private int Moves[][] = new int[][] {{2, 1}, {2, -1}, {1, 2}, {1, -2}, {-2, 1}, {-2, -1}, {-1, 2}, {-1, -2}};

void solveKnightTour(int[][] board)
{
    knightsTourUtil(board, 0, 0, 1);
}

private boolean isSafeMove(int[][] board, int r, int c)
{
    if(r < 0 && r > board.length-1 && c < 0 && c > board.length-1 &&  board[r][c] != -1)
        return false;
    return true;
}

private boolean knightsTourUtil(int[][] board, int presentRow, int presentCol, int KthMove)
{
    if (KthMove >= MaxMove)
    {
        return true;
    }
    for (int i = 0; i < Moves.length; i++)
    {
        int nextRow = presentRow + Moves[i][0];
        int nextCol = presentCol + Moves[i][1];
        if (isSafeMove(board, nextRow, nextCol))
        {
            board[nextRow][nextCol] = KthMove;
            if (knightsTourUtil(board, nextRow, nextCol, KthMove + 1)) 
                return true;
            else
                board[nextRow][nextCol] = -1;
        }
    }
    return false;
}

Answer 1

您收到异常是因为您尝试访问索引超出数组范围的元素。

发生这种情况是因为 isSafeMove 方法中的 if 语句没有执行您希望它执行的操作。

if(r < 0 && r > board.length-1 && c < 0 && c > board.length-1 &&  board[r][c] != -1)

您使用了 &&，因此所有这些语句在 other 中都需要为 true 才能执行 if block ，而不是 && 如果其中只有 1 个情况为真，则应在 other 中使用 || 才能使其正常工作。

像这样:

if(r < 0 || r > board.length-1 || c < 0 || c > board.length-1 ||  board[r][c] != -1)

编辑起初我以为 -1 代表未访问过的字段，但事实证明 -1 代表访问过的字段。如果应该看起来像这样:

if(r < 0 || r > board.length-1 || c < 0 || c > board.length-1 ||  board[r][c] == -1)