import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { static int getSerial(int[] data) { return data[0]; } static int get_i(int[] data) { return data[1]; } static int get_j(int[] data) { return data[2]; } static int[] create(int s,int i, int j) { int[] data = new int[3]; data[0] = s; data[1] = i; data[2] = j; return data; } static void traverse(int[][] board, int n, int i, int j) { int[] off_i = {-2,-2,0,2,2,0}; int[] off_j = {-1,1,2,1,-1,-2}; int serial = 0; Queue q = new PriorityQueue<>((d1,d2)->d1[0]-d2[0]); q.add(create(serial++,i,j)); while (!q.isEmpty()){ int[] c_data = q.poll(); int c_i = get_i(c_data); int c_j = get_j(c_data); for(int k=0;k<6;k++){ int n_i = c_i + off_i[k]; int n_j = c_j+off_j[k]; if(n_i<0 || n_i>=n || n_j<0 || n_j>=n){ continue; } boolean pristine = board[n_i][n_j] == Integer.MAX_VALUE; board[n_i][n_j] = Math.min(board[n_i][n_j], board[c_i][c_j]+1); if(pristine){ int[] data = create(serial++,n_i,n_j); q.add(data); } } } } static void findPath(int[][] board, int n, int i, int j, int cost,ArrayList path, String nm, int d_i,int d_j) { if(i<0 || i>=n || j<0 || j>=n){ return ; } if(board[i][j] != cost) return ; if(nm!=null) path.add(nm); if(i == d_i && j == d_j){ board[d_i][d_j] = -1; } int[] off_i = {-2,-2,0,2,2,0}; int[] off_j = {-1,1,2,1,-1,-2}; String[] name = {"UL","UR","R","LR","LL","L"}; for(int k=0;k<6&&board[d_i][d_j]>=0;k++){ findPath(board,n,i+off_i[k],j+off_j[k],cost-1, path, name[k], d_i,d_j); } } static void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { // Print the distance along with the sequence of moves. int[][] board = new int[n][n]; for(int[] arr : board)Arrays.fill(arr,Integer.MAX_VALUE); board[i_end][j_end] = 0; traverse(board,n,i_end,j_end); if(board[i_start][j_start] == Integer.MAX_VALUE) { System.out.println("Impossible"); return; } ArrayList arrayList = new ArrayList<>(); int cost = board[i_start][j_start]; findPath(board,n,i_start,j_start,cost,arrayList,null,i_end,j_end); System.out.println(cost); for(int i=0;i