#include using namespace std; #define MOD 1000000007 #define mk make_pair //#define ff first //#define ss second #define pb push_back void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { vector > visited(n, vector (n, 1000000)); vector > > parent(n, vector >(n)); queue > q; q.push(mk(i_start, j_start)); visited[i_start][j_start]=0; while(!q.empty()){ i_start = q.front().first; j_start = q.front().second; //cout<=0 && j_start-1>=0 && visited[i_start-2][j_start-1]==1000000){ visited[i_start-2][j_start-1] = visited[i_start][j_start]+1; parent[i_start-2][j_start-1].first=-2; parent[i_start-2][j_start-1].second=-1; q.push(mk(i_start-2, j_start-1)); } // UR if(i_start-2>=0 && j_start+1=0 && visited[i_start+2][j_start-1]==1000000){ visited[i_start+2][j_start-1] = visited[i_start][j_start]+1; parent[i_start+2][j_start-1].first = 2; parent[i_start+2][j_start-1].second = -1; q.push(mk(i_start+2, j_start-1)); } // L if(j_start-2>=0 && visited[i_start][j_start-2]==1000000){ visited[i_start][j_start-2] = visited[i_start][j_start]+1; parent[i_start][j_start-2].first = 0; parent[i_start][j_start-2].second = -2; q.push(mk(i_start, j_start-2)); } } if(visited[i_end][j_end]==1000000){ cout<<"Impossible"; return; } cout< ans; while(visited[i_end][j_end]>0){ if(parent[i_end][j_end]==mk(-2, -1)){ ans.pb("UL"); } else if(parent[i_end][j_end]==mk(-2, 1)){ ans.pb("UR"); } else if(parent[i_end][j_end]==mk(0, 2)){ ans.pb("R"); } else if(parent[i_end][j_end]==mk(2, 1)){ ans.pb("LR"); } else if(parent[i_end][j_end]==mk(2, -1)){ ans.pb("LL"); } else{ ans.pb("L"); } int temp=i_end-parent[i_end][j_end].first; j_end-=parent[i_end][j_end].second; i_end=temp; //cout<=0; 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; }