import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { private static int[] temp = new int[2]; private static int counts = 0; static void printShortestPath(int n, int j_start, int i_start, int j_end, int i_end, int i_temp, int j_temp) { // Print the distance along with the sequence of moves. int[] route = new int[6]; if(Math.abs(j_end - j_start)%2 == 1){ System.out.println("Impossible"); return; } i_temp = i_start; j_temp = j_start; //go up first if((j_end-j_start)<0){ //go y while(j_temp!=j_end){ //x same if(i_end==i_start){ temp = moveStep(i_temp,j_temp,"UL"); i_temp = temp[0]; j_temp = temp[1]; temp = moveStep(i_temp,j_temp,"UR"); i_temp = temp[0]; j_temp = temp[1]; route[0] = route[0]+1; route[1] = route[1]+1; } // left else if(i_end-i_start<0){ temp = moveStep(i_temp,j_temp,"UL"); i_temp = temp[0]; j_temp = temp[1]; route[0] = route[0]+1; } // right else { temp = moveStep(i_temp,j_temp,"UR"); i_temp = temp[0]; j_temp = temp[1]; route[1] = route[1]+1; } } //go x if(Math.abs(i_end - i_temp)%2 == 1){ System.out.println("Impossible"); return; } moveX(i_temp, j_temp, i_end, i_start, route); } //same level else if(j_end == j_start){ if(Math.abs(i_end - i_temp)%2 == 1){ System.out.println("Impossible"); return; } moveX(i_temp, j_temp, i_end, i_start, route); } // down else { //go y while(j_temp!=j_end){ //x same if(i_end==i_start){ temp = moveStep(i_temp,j_temp,"LL"); i_temp = temp[0]; j_temp = temp[1]; temp = moveStep(i_temp,j_temp,"LR"); i_temp = temp[0]; j_temp = temp[1]; route[4] = route[4]+1; route[3] = route[3]+1; } // left else if(i_end-i_start<0){ temp = moveStep(i_temp,j_temp,"LL"); i_temp = temp[0]; j_temp = temp[1]; route[4] = route[4]+1; } // right else { temp = moveStep(i_temp,j_temp,"LR"); i_temp = temp[0]; j_temp = temp[1]; route[3] = route[3]+1; } } if(Math.abs(i_end - i_temp)%2 == 1){ System.out.println("Impossible"); return; } //go x moveX(i_temp, j_temp, i_end, i_start, route); } printRoute(route); } private static void moveX(int i_temp, int j_temp, int i_end, int i_start, int[] route){ //go x while(Math.abs(i_temp-i_end)/2/2 != 0){ //left if(i_end-i_start<0){ temp = moveStep(i_temp,j_temp,"UL"); i_temp = temp[0]; j_temp = temp[1]; temp = moveStep(i_temp,j_temp,"LL"); i_temp = temp[0]; j_temp = temp[1]; route[0] = route[0]+1; route[4] = route[4]+1; } // right else { temp = moveStep(i_temp,j_temp,"UR"); i_temp = temp[0]; j_temp = temp[1]; temp = moveStep(i_temp,j_temp,"LR"); i_temp = temp[0]; j_temp = temp[1]; route[1] = route[1]+1; route[3] = route[3]+1; } } if(i_temp != i_end){ //left if(i_end-i_start<0){ temp = moveStep(i_temp,j_temp,"L"); i_temp = temp[0]; j_temp = temp[1]; route[5] = route[5]+1; } // right else { temp = moveStep(i_temp,j_temp,"R"); i_temp = temp[0]; j_temp = temp[1]; route[2] = route[2]+1; } } } private static void printRoute(int[] route){ String[] steps = {"UL","UR","R","LR","LL","L"}; System.out.println(counts); for(int i=0;i