import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { static int n = 0; static final String[] moves = {"UL","UR","R","LR","LL","L"}; static int min_distance = 9999; static String min_path=""; static int fun_count=0; //4 sec static void printShortestPath(int y, int x, int ye, int xe) { // Print the distance along with the sequence of moves. int[] distance={0,0,0}; String history="HISTORY:"+"["+y+x+"]"; String path=""; for(int i=0; i<6; i++){ //System.out.println("-----------Moving ->"+moves[i]+"["+y+x+"]"); distance=step6(distance,history,path, moves[i],y,x,ye,xe); if(distance[1]<0){ distance[1]=0; continue; } else if(distance[1]==1){ System.out.println("FINAL SUCCESS*************"); distance[1]=0; distance[0]=0; continue; } } //System.out.println("######################################"); if(distance[2]==0){ System.out.println("Impossible"); } else{ System.out.println(min_distance); System.out.println(min_path); } } static int[] step6(int[] distance,String history,String path,String move_type, int y, int x, int ye, int xe){ //System.out.println("STATUS------------------------DISTANCE:"+distance[0]+" and MAX:"+distance[2]); fun_count++; if (fun_count>4000){ distance[2]=0; return distance; } if (distance[1]==1){ return distance; //skip one position } if (distance[2]!=0 && (distance[0]>distance[2]-1)){ distance[1]=-1; return distance; } int[] new_pos = move(move_type,y,x); if (new_pos[0]==-1){ //System.out.println("INVALID MOVE"); distance[1]=-1; return distance; } else if (new_pos[0]==ye && new_pos[1]==xe){ distance[0]++; distance[1]=1; //success distance[2]=distance[0]; path+=move_type+" "; history+="["+new_pos[0]+new_pos[1]+"]"; //System.out.println("SUCCESS @ DIST:"+distance[2] + "path is:"+history+"PATH>>"+path); if(distance[2]"+moves[i]+"["+new_pos[0]+new_pos[1]+"]"); distance=step6(distance,history,path, moves[i],new_pos[0],new_pos[1],ye,xe); if(distance[1]<0){ distance[1]=0; continue; } else if(distance[1]==1){ //System.out.println("Recursive SUCCESS*************"); distance[1]=0; distance[0]--; return distance; } } } distance[0]--; return distance; } static int[] move(String move_type,int y, int x){ // Rules for moving switch (move_type){ case "UL": y-=2; x--; break; case "UR": y-=2; x++; break; case "R": x+=2; break; case "LR": y+=2; x++; break; case "LL": y+=2; x--; break; case "L": x-=2; break; default: //System.out.println("Error Move"); break; } //checking move gone outside board //System.out.println("MOOVER:"+y+x); if(x>=0 && y>=0 && x