# Untitled

unknown
plain_text
12 days ago
1.2 kB
14
Indexable
Never
```public class Solution {

public static int[][] knightTour(int n, int m) {
int[][] chessBoard = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
chessBoard[i][j] = -1;
}
}

chessBoard[0][0] = 0;
int[] rowArray = { 1, -1, 2, 2, -1, 1, -2, -2 };
int[] colArray = { 2, 2, -1, 1, -2, -2, -1, 1 };

knightTour2(chessBoard, rowArray, colArray, 1, 0, 0, n, m);

return chessBoard;

}

public static boolean knightTour2(int[][] board, int[] rowA, int[] colA, int step, int currR, int currC, int n,
int m) {
if (step == n * m)
return true;

for (int i = 0; i < 8; i++) {
int nextR = currR + rowA[i];
int nextC = currC + colA[i];
if (isValidMove(board, nextR, nextC,n,m)) {
board[nextR][nextC] = step;
boolean flag = knightTour2(board, rowA, colA, step + 1, nextR, nextC, n,m);
if (flag)
return true;
else {
board[nextR][nextC] = -1;
}
}
}
return false;

}

public static boolean isValidMove( int[][] board, int r, int c, int n, int m) {
return (r >= 0 && c >= 0 && r<n && c<m && board[r][c] == -1);

}

}
```