#include using namespace std; string solve (int n , int x , int y , int x1 , int y1 , string ans) { if ( x<0 || y<0 || x>=n || y>=n) return "Impossible"; else if ( x==x1 && y==y1) return ans; else { string tmp[6],result; int size=INT_MAX; tmp[0] = solve (n,x-2,y-1,x1,y1,ans+"UL "); tmp[1] = solve (n,x-2,y+1,x1,y1,ans+"UR "); tmp[2] = solve (n,x,y+2,x1,y1,ans+"R "); tmp[3] = solve(n,x+2,y+1,x1,y1,ans+"LR "); tmp[4] = solve(n,x+2,y-1,x1,y1,ans+"LL "); tmp[5] = solve(n,x,y-2,x1,y1,ans+"L "); for ( int i=0;i<6;i++) { if (tmp[i]!="Impossible") { if(size>tmp[i].size()) result=tmp[i]; size = result.size(); } } return result; } } 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. //string ans = solve(n,i_start,j_start,i_end,j_end," "); //cout<=count) { string ans; int size=0,y; size+=count; if(j_start>j_end) { y=j_start-count; while(count--) { ans+= string("LL "); } } else if (j_startj_end) { while(count2--) { ans+= string("L "); } } else if (yj_start) while(z--) { ans+= string(pp); } int t=(count-count2)/2; while(t--) { ans+=(pp+pp2); size+=2; } if( (count-count2)%2!=0) { ans+=pp2; size++; if(pp2=="LL ") y+=-2; else y+=2; } if (abs(y-j_end)%2==0) { int count3=abs(y-j_end)/2; if(yi_end) { if ( count2>count) { string ans; int size=0,y; size+=count; if(j_start>j_end) { y=j_start-count; while(count--) { ans+= string("UL "); } } else if (j_startj_end) { while(count2--) { ans+= string("L "); } } else if (yj_start) { t=(count-count2)/2; while(t--) { ans+=(pp+pp2); size+=2; } pp="UR "; pp2="UL "; int z=count2; while(z--) { ans+=string(pp); } } else if (j_end>j_start) { int z=count2; while(z--) { ans+=string(pp); } t=(count-count2)/2; while(t--) { ans+=(pp+pp2); size+=2; } } if( (count-count2)%2!=0) { ans+=pp2; size++; if(pp2=="UL ") y+=-2; else y+=2; } if (abs(y-j_end)%2==0) { int count3=abs(y-j_end)/2; if(yj_end && (j_start-j_end)%2==0) { count = (j_start-j_end)/2; while(count--) { cout<<"L "; } } else if (j_start> n; int i_start; int j_start; int i_end; int j_end; cin >> i_start >> j_start >> i_end >> j_end; printShortestPath(n, i_start, j_start, i_end, j_end); return 0; }