#include using namespace std; #define pb push_back #define ff first #define ss second #define maxn 100005 #define mk make_pair #define PI 3.14159265 #define INF 1000000000 #define mod 1000000007 #define pii pair #define SZ(X) ((int)(X).size()) #define ALL(X) (X).begin(), (X).end() #define uniq(v) sort(ALL(v));v.erase(unique(ALL(v)),v.end()) #define REP(I, N) for (int I = 0; I < (N); ++I) #define REPP(I, A, B) for (int I = (A); I <= (B); ++I) #define REPD(I, N) for (int I = N; I >=0; I--) #define _ ios::sync_with_stdio(false);cin.tie(0); #define trace1(x) cout << #x << ": " << x << endl; #define trace2(x, y) cout << #x << ": " << x << " | " << #y << ": " << y << endl; #define trace3(x, y, z) cout << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl; #define trace4(x, y, z, w) cout << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << " | " << #w <<": "<< w << endl; #define trace5(x, y, z, w, t) cout << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << " | " << #w <<": "<< w << " | " << #t << ": " << t < &here,int now,int n){ int x = vp.ff, y = vp.ss; if(y-1 >= 0 && x - 2 >= 0) {if(d[x-2][y-1] > now +1) {d[x-2][y-1] = now + 1; pre[x-2][y-1] = vp; preC[x-2][y-1] = "UL"; here.pb(mk(x-2,y - 1)); }} if(y+1 < n && x - 2 >= 0) { if(d[x-2][y+1] > now +1) {d[x-2][y+1] = now + 1; pre[x-2][y+1] = vp; preC[x-2][y+1] = "UR"; here.pb(mk(x-2,y+1)); }} if(y+2 < n) { if(d[x][y+2] >now +1) {d[x][y+2] = now + 1; pre[x][y+2] = vp; preC[x][y+2] = "R"; here.pb(mk(x,y+2)); }} if(y+1 < n && x + 2 < n) { if(d[x+2][y+1] > now +1) {d[x+2][y+1] = now + 1; pre[x+2][y+1] = vp; preC[x+2][y+1] = "LR"; here.pb(mk(x+2,y+1)); }} if(y-1 >= 0 && x + 2 < n) {if(d[x+2][y-1] > now +1) {d[x+2][y-1] = now + 1; pre[x+2][y-1] = vp; preC[x+2][y-1] = "LL"; here.pb(mk(x+2,y - 1)); }} if(y-2 >= 0) {if(d[x][y-2] > now +1) {d[x][y-2] = now + 1; pre[x][y-2] = vp; preC[x][y-2] = "L"; here.pb(mk(x,y-2)); }} } 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. vector vp; vp.pb(mk(i_start,j_start)); for(int i = 0;i < n;i++){ for(int j = 0;j < n;j++){ d[i][j] = INF; } } d[i_start][j_start] = 0; for(int i = 0;i < n*n;i++){ vector here; for(int j = 0;j < vp.size();j++){ make_d(vp[j],here,i,n); } vp.clear(); vp = here; here.clear(); } if(d[i_end][j_end] == INF){ cout<<"Impossible\n"; return; } cout< ans; int x,y; x = i_end; y = j_end; pii req = mk(i_start,j_start); while(pre[x][y]!=req){ ans.pb(preC[x][y]); int xx = pre[x][y].ff; y = pre[x][y].ss; x = xx; } ans.pb(preC[x][y]); reverse(ALL(ans)); for(int i = 0;i < ans.size();i++){ cout<> 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; }