骑士之旅- BackTracking在爪哇，越界

Question

我试图解决的问题是，给定一个N*M棋盘，骑士之旅被定义为骑士的一系列移动，使得骑士只访问每个方块一次。下面是我的代码，但是我让数组越界= 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

你会得到这个exception，因为你尝试用索引访问元素，这超出了你的数组的界限。

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

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

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

如下所示：

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

编辑一开始我以为-1表示未访问的字段，但事实证明-1表示已访问的字段。If应如下所示：

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