import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { 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. boolean moveI = false; boolean moveJ =false; List pathList = new ArrayList(); int stepsUp, stepsDown,stepsLeft,stepsRight = 0; String direction = "none"; int steps = 0; boolean possible = false; int totalSteps = 0; // case :(5,5)(5,4) ---> just horizontal movement if (i_start == i_end) moveJ = true; //means moving horizontal( left or right ) else if(j_start == j_end) moveI = true; if(moveJ){ if(j_start < j_end){ stepsRight = j_end-j_start; if (stepsRight % 2 == 0){ stepsRight = stepsRight/2; System.out.println(stepsRight); for(int i =0;i < stepsRight; i++) System.out.print("R "); return; }else{ System.out.print("Impossible"); return; } } else{ stepsLeft= j_start - j_end; if (stepsLeft % 2 == 0){ stepsLeft = stepsLeft/2; System.out.println(stepsLeft); for(int i =0;i < stepsLeft; i++) System.out.print("L "); return; }else{ System.out.print("Impossible"); return; } } } /////// ----> just vertical movement case: (4,5)(6,5) if(moveI){ if(i_start < i_end){ stepsDown = i_end - i_start; if(stepsDown % 2 == 0 && stepsDown>2){ stepsDown = stepsDown/2; System.out.println(stepsDown); for(int i = 1; i <= stepsDown; i++){ if(i % 2 != 0) System.out.print("LR "); else System.out.print("LL "); } return; }else{ System.out.print("Impossible"); return; } }else{ stepsUp= i_start - i_end; if(stepsUp % 2 == 0 && stepsUp >2){ stepsUp = stepsUp/2; System.out.println(stepsUp); for(int i = 1; i <= stepsUp; i++){ if(i % 2 != 0) System.out.print("UR "); else System.out.print("UL "); } return; }else{ System.out.print("Impossible"); return; } } } //////////////////// normal case ( 4,1)(6,3) moving down if (j_start < j_end) direction = "right"; else direction = "left"; if(i_start < i_end && direction.equals("right")){ stepsDown = i_end - i_start; stepsRight = (j_end - j_start)- (stepsDown/2); if((stepsDown % 2 == 0) && stepsDown > 2 && (stepsRight %2 == 0) && stepsRight>= 2){ totalSteps = stepsDown/2 + stepsRight/2; for(int i =0; i<(stepsDown/2); i++) pathList.add("LR"); for(int i =0; i<(stepsRight/2); i++) pathList.add("R"); }else{ System.out.println("Impossible"); return; } } else if (i_start < i_end && direction.equals("left")){ stepsDown = i_end - i_start; stepsLeft = (j_start -j_end) - (stepsDown/2); if((stepsDown % 2 == 0) && stepsDown > 2 && (stepsLeft %2 == 0) && stepsLeft>= 2){ totalSteps = stepsDown/2 + stepsLeft/2; for(int i =0; i<(stepsDown/2); i++) pathList.add("LL"); for(int i =0; i<(stepsLeft/2); i++) pathList.add("L"); }else{ System.out.println("Impossible"); return; } }else if(i_start > i_end && direction.equals("right")){ stepsUp = i_start -i_end; stepsRight = (j_end - j_start)- (stepsUp/2); if((stepsUp % 2 == 0) && stepsUp > 2 && (stepsRight %2 == 0) && stepsRight>= 2){ totalSteps = stepsUp/2 + stepsRight/2; for(int i =0; i<(stepsUp/2); i++) pathList.add("UR"); for(int i =0; i<(stepsRight/2); i++) pathList.add("R"); }else{ System.out.println("Impossible"); return; } }else if(i_start > i_end && direction.equals("left")){ stepsUp = i_start -i_end; stepsLeft = (j_start - j_end)- (stepsUp/2); if((stepsUp % 2 == 0) && stepsUp > 2 && (stepsLeft %2 == 0) && stepsLeft>= 2){ totalSteps = stepsUp/2 + stepsLeft/2; for(int i =0; i<(stepsUp/2); i++) pathList.add("UL"); for(int i =0; i<(stepsLeft/2); i++) pathList.add("L"); }else{ System.out.println("Impossible"); return; } } System.out.println(totalSteps); for(int i =0; i