Untitled

mail@pastecode.io avatar
unknown
java
22 days ago
1.6 kB
3
Indexable
Never
public class Solution {

  static boolean knightsTourHelper(int n,int m, int a[][], int movesX[],int movesY[], int curX, int curY, int step) {

        if(step == n*m) return true;

        for(int i = 0; i<8; i++) {
            int nextX = curX + movesX[i];
            int nextY = curY + movesY[i];
            if(isValid(n,m, a, nextX, nextY)) {
                a[nextX][nextY] = step;
                boolean isTourCompletedByGoingThere =
                        knightsTourHelper(n,m, a, movesX, movesY, nextX, nextY, step+1);
                if(isTourCompletedByGoingThere) {
                    return true;
                } else {
                    a[nextX][nextY] = -1;
                }
            }
        }

        return false;
    }

    static boolean isValid(int n,int m, int a[][], int x, int y) {
        return x >= 0 && y >= 0 && x < n && y < m && a[x][y] == -1;
    }
  
    public static int[][] knightTour(int n, int m) {
        //You can code here

        int a[][] = new int[n][m];
        for(int i = 0; i<n; i++) {
            for(int j = 0; j<m; j++) {
                a[i][j] = -1;
            }
        }
        a[0][0] = 0;
        int movesX[] = {2, 1, -1, -2, -2, -1, 1, 2};
        int movesY[] = {1, 2, 2, 1, -1, -2, -2, -1};

        boolean res=knightsTourHelper(n,m, a, movesX, movesY, 0, 0, 1);

        if(res)
        return a;
        else{
for(int i = 0; i<n; i++) {
            for(int j = 0; j<m; j++) {
                a[i][j] = -1;
            }

            
        }
return a;
        }


        
        
    }
}
Leave a Comment