import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; class Node{ int moves; int cx,cy,px,py; String mv=""; public Node(int moves,int cx,int cy,int px,int py,String mv){ this.moves=moves; this.cx=cx; this.cy=cy; this.px=px; this.py=py; this.mv=mv; } } 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. Node mat[][]=new Node[n][n]; int i,j; if(!isValid(i_start,j_start,n)){ System.out.println("Impossible"); return; } if(!isValid(i_end,j_end,n)){ System.out.println("Impossible"); return; } for(i=0;i que=new LinkedList<>(); que.add(new Node(0,i_start,j_start,i_start,j_start,"")); Node cn=mat[i_start][j_start]; //cn.moves=0; int cncx,cncy,cnmoves,cnpx,cnpy; int dx[]={-2,-2,0,2,2,0}; int dy[]={-1,1,2,1,-1,-2}; int mnx,mny; Node mnode; while(!que.isEmpty()){ cn=que.remove(); cncx=cn.cx; cncy=cn.cy; cnmoves=cn.moves; cnpx=cn.px; cnpy=cn.py; Node mcn=mat[cncx][cncy]; if(mcn.moves>cnmoves){ mcn.moves=cnmoves; mcn.px=cnpx; mcn.py=cnpy; mcn.mv=cn.mv; mat[cncx][cncy]=cn; for(i=0;i<6;i++){ switch(i){ case 0: mnx=cncx+dx[i]; mny=cncy+dy[i]; if(isValid(mnx,mny,n)){ mnode=mat[mnx][mny]; if(mnode.moves>cnmoves+1){ Node mnew=new Node(cnmoves+1,mnx,mny,cncx,cncy,"UL"); que.add(mnew); // mat[mnx][mny]=mnew; } } case 1: mnx=cncx+dx[i]; mny=cncy+dy[i]; if(isValid(mnx,mny,n)){ mnode=mat[mnx][mny]; if(mnode.moves>cnmoves+1){ Node mnew=new Node(cnmoves+1,mnx,mny,cncx,cncy,"UR"); que.add(mnew); //mat[mnx][mny]=mnew; } } case 2: mnx=cncx+dx[i]; mny=cncy+dy[i]; if(isValid(mnx,mny,n)){ mnode=mat[mnx][mny]; if(mnode.moves>cnmoves+1){ Node mnew=new Node(cnmoves+1,mnx,mny,cncx,cncy,"R"); que.add(mnew); // mat[mnx][mny]=mnew; } } case 3: mnx=cncx+dx[i]; mny=cncy+dy[i]; if(isValid(mnx,mny,n)){ mnode=mat[mnx][mny]; if(mnode.moves>cnmoves+1){ Node mnew=new Node(cnmoves+1,mnx,mny,cncx,cncy,"LR"); que.add(mnew); // mat[mnx][mny]=mnew; } } case 4: mnx=cncx+dx[i]; mny=cncy+dy[i]; if(isValid(mnx,mny,n)){ mnode=mat[mnx][mny]; if(mnode.moves>cnmoves+1){ Node mnew=new Node(cnmoves+1,mnx,mny,cncx,cncy,"LL"); que.add(mnew); // mat[mnx][mny]=mnew; } } case 5: mnx=cncx+dx[i]; mny=cncy+dy[i]; if(isValid(mnx,mny,n)){ mnode=mat[mnx][mny]; if(mnode.moves>cnmoves+1){ Node mnew=new Node(cnmoves+1,mnx,mny,cncx,cncy,"L"); que.add(mnew); // mat[mnx][mny]=mnew; } } } } } } int res=mat[i_end][j_end].moves; if(res==Integer.MAX_VALUE){ System.out.println("Impossible"); return; } // display(mat,n); ArrayList order=new ArrayList<>(); Node end=mat[i_end][j_end]; cncx=end.cx; cncy=end.cy; cnpx=end.px; cnpy=end.py; // order.add(end.mv); while(cncx!=cnpx || cncy!=cnpy){ order.add(mat[cncx][cncy].mv); //System.out.println("cncx="+cncx+" cncy="+cncy+" cnpx="+cnpx+" cnpy="+cnpy+" mv="+mat[cncx][cncy].mv); int temp_cnpx=mat[cnpx][cnpy].px; int temp_cnpy=mat[cnpx][cnpy].py; cncx=cnpx; cncy=cnpy; cnpx=temp_cnpx; cnpy=temp_cnpy; } System.out.println(res); for(i=res-1;i>=0;i--){ System.out.print(order.get(i)+" "); } } static void display(Node mat[][],int n){ for(int i=0;i ",cn.moves,cn.cx,cn.cy,cn.px,cn.py,cn.mv); } System.out.println(); } } static boolean isValid(int x,int y,int n){ if(x>=0 && x=0 && y