Untitled
unknown
plain_text
a year ago
1.2 kB
20
Indexable
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); } }
Editor is loading...
Leave a Comment