#include #define x first #define y second using namespace std; typedef pair pii; pii operator+(pii a, pii b) {return {a.x + b.x, a.y + b.y};} bool operator==(pii a, pii b) {return (a.x == b.x && a.y == b.y);} inline bool inside(pii a, int n) { return ((a.x >= 0 && a.x < n) && (a.y >= 0 && a.y < n)); } struct Node{ pii coords; Node* prev; string path; }; inline void init(Node*& cur, pii c, Node* p=0, string pa=" ") { cur->coords = c; cur->prev = p; cur->path = pa; } void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { vector moves = {{-2, -1}, {-2, 1}, {0, 2}, {2, 1}, {0, -2}, {2, -1}}; vector way = {"UL", "UR", "R", "LR", "L", "LL"}; bool used[n][n]; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) used[i][j] = 0; queue Q; Node* f = new Node; init(f, {i_start, j_start}); Q.push(f); bool check = true; int counter = 0; while (!Q.empty() && check) { if (counter++ > 40000) { cout << "Impossible" << endl; return; } Node* cur = Q.front(); Q.pop(); used[cur->coords.x][cur->coords.y] = 1; for (int i = 0; i < 6; i++) { pii loc = moves[i]+cur->coords; if (inside(loc, n) && !used[loc.x][loc.y]) { Node* no = new Node; init(no, loc, cur, way[i]); Q.push(no); if (loc == make_pair(i_end, j_end)) { check = false; break; } } } } if (Q.empty() || check) cout << "Impossible" << endl; else if (!check){ vector ans; Node* cur = Q.back(); while (cur->prev) { ans.push_back(cur->path); cur = cur->prev; } reverse(ans.begin(), ans.end()); cout << ans.size() << endl; for (string s : ans) cout << s << " "; } } 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; }