#include #include #include #include #include #include #include #include #include //Print a vector as string seperated by space //std::copy(distance.begin(), distance.end(), std::ostream_iterator(result, " ")); using namespace std; typedef long long LL; typedef vector VI; typedef vector VB; typedef vector VS; typedef vector VVI; typedef vector VVB; typedef list LS; typedef pair PII; typedef pair PIC; typedef vector VPII; typedef unordered_map UMSI; typedef set SI; typedef unordered_set USI; typedef tuple TIII; #define _F first #define _S second #define _PB push_back #define _MP make_pair #define _SZ size() #define _B begin() #define _E end() #define _RB rbegin() #define _RE rend() typedef stringstream SS; typedef istringstream ISS; typedef ostringstream OSS; //Print a vector as string seperated by space //std::copy(distance.begin(), distance.end(), std::ostream_iterator(result, " ")); struct node { node() { jumps = 0; start = false; } int X; int Y; int prevX; int prevY; LS jumpsMade; int jumps; bool start; }; void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { VVB visited(n, VB(n, false)); int total = n*n; queue Q; node start; start.X = i_start; start.Y = j_start; start.start = true; Q.push(start); node end; while(!Q.empty()) { node next = Q.front(); Q.pop(); if(visited[next.X][next.Y] == false) { visited[next.X][next.Y] = true; node UL, UR, R, LR, LL, L; if(next.X - 1 >= 0 && next.Y - 2 >= 0) { UL.X = next.X - 1; UL.Y = next.Y - 2; UL.prevX = next.X; UL.prevY = next.Y; UL.jumps = next.jumps + 1; UL.jumpsMade = next.jumpsMade; UL.jumpsMade.push_back("UL"); if(UL.X == i_end && UL.Y == j_end) { end = UL; break; } else { Q.push(UL); } } if(next.X + 1 < n && next.Y - 2 >= 0) { UR.X = next.X + 1; UR.Y = next.Y - 2; UR.prevX = next.X; UR.prevY = next.Y; UR.jumps = next.jumps + 1; UR.jumpsMade = next.jumpsMade; UR.jumpsMade.push_back("UR"); if(UR.X == i_end && UR.Y == j_end) { end = UR; break; } else { Q.push(UR); } } if(next.X + 2 < n) { R.X = next.X + 2; R.Y = next.Y; R.prevX = next.X; R.prevY = next.Y; R.jumps = next.jumps + 1; R.jumpsMade = next.jumpsMade; R.jumpsMade.push_back("R"); if(R.X == i_end && R.Y == j_end) { end = R; break; } else { Q.push(R); } } if(next.X + 1 < n && next.Y + 2 < n) { LR.X = next.X + 1; LR.Y = next.Y + 2; LR.prevX = next.X; LR.prevY = next.Y; LR.jumps = next.jumps + 1; LR.jumpsMade = next.jumpsMade; LR.jumpsMade.push_back("LR"); if(LR.X == i_end && LR.Y == j_end) { end = LR; break; } else { Q.push(LR); } } if(next.X - 1 >= 0 && next.Y + 2 < n) { LL.X = next.X - 1; LL.Y = next.Y + 2; LL.prevX = next.X; LL.prevY = next.Y; LL.jumps = next.jumps + 1; LL.jumpsMade = next.jumpsMade; LL.jumpsMade.push_back("LL"); if(LL.X == i_end && LL.Y == j_end) { end = LL; break; } else { Q.push(LL); } } if(next.X - 2 >= 0) { L.X = next.X - 2; L.Y = next.Y; L.prevX = next.X; L.prevY = next.Y; L.jumps = next.jumps + 1; L.jumpsMade = next.jumpsMade; L.jumpsMade.push_back("L"); if(L.X == i_end && L.Y == j_end) { end = L; break; } else { Q.push(L); } } } } if(end.X == i_end && end.Y == j_end) { std::copy(end.jumpsMade.begin(), end.jumpsMade.end(), std::ostream_iterator(cout, " ")); } else { cout << "Impossible" << endl; } } int main() { int n; cin >> 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; }