#include using namespace std; bool isSafe(int x,int y,int n){ if(x >= 0 && x < n && y >= 0 && y < n) return true; return false; } 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< pair< pair , pair< pair,string > > > q; vector path; q.push_back(make_pair(make_pair(i_start,j_start),make_pair(make_pair(0,-1),""))); vector> visited(n,vector(n,false)); visited[i_start][j_start] = true; int f=0,r=0,res=-1,ind=-1; while(f <= r){ int x = q[f].first.first; int y = q[f].first.second; int d = q[f].second.first.first; int par = q[f].second.first.second; if(x == i_end && y == j_end){ res = d; ind = f; break; } if(isSafe(x-2,y-1,n) && !visited[x-2][y-1]){ q.push_back(make_pair(make_pair(x-2,y-1),make_pair(make_pair(d+1,f),"UL"))); path.push_back("UL"); visited[x-2][y-1] = true; r++; } if(isSafe(x-2,y+1,n) && !visited[x-2][y+1]){ q.push_back(make_pair(make_pair(x-2,y+1),make_pair(make_pair(d+1,f),"UR"))); path.push_back("UR"); visited[x-2][y+1] = true; r++; } if(isSafe(x,y+2,n) && !visited[x][y+2]){ q.push_back(make_pair(make_pair(x,y+2),make_pair(make_pair(d+1,f),"R"))); path.push_back("R"); visited[x][y+2] = true; r++; } if(isSafe(x+2,y+1,n) && !visited[x+2][y+1]){ q.push_back(make_pair(make_pair(x+2,y+1),make_pair(make_pair(d+1,f),"LR"))); path.push_back("LR"); visited[x+2][y+1] = true; r++; } if(isSafe(x+2,y-1,n) && !visited[x+2][y-1]){ q.push_back(make_pair(make_pair(x+2,y-1),make_pair(make_pair(d+1,f),"LL"))); path.push_back("LL"); visited[x+2][y-1] = true; r++; } if(isSafe(x,y-2,n) && !visited[x][y-2]){ q.push_back(make_pair(make_pair(x,y-2),make_pair(make_pair(d+1,f),"L"))); path.push_back("L"); visited[x][y-2] = true; r++; } f++; } if(res == -1) cout<<"Impossible"; else{ cout< st; while(ind != 0){ st.push(q[ind].second.second); ind = q[ind].second.first.second; } while(!st.empty()){ 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; }