#include #include #include #include #include #include #include #include using namespace std; vector> steps = { {-2, -1}, {-2, 1}, {0, 2}, {2, 1}, {2, -1}, {0, -2} }; vector moves = {"UL", "UR", "R", "LR", "LL", "L"}; unordered_map movesOrder = { {"UL", 1}, {"UR", 2}, {"R", 3}, {"LR", 4}, {"LL", 5}, {"L", 6} }; bool operator> (const vector& v1, const vector& v2) { int n = v1.size(); for (int i = 0; i < n; i++) { if (movesOrder[v1[i]] != movesOrder[v2[i]]) { return movesOrder[v1[i]] > movesOrder[v2[i]]; } } return false; } struct Point { int r, c, d; vector path; bool operator> (const Point x) const { return d > x.d || (d == x.d && path > x.path); } Point(int y, int x, int l, vector& v): r(y), c(x), d(l), path(v) {} }; int main() { int n, r1, c1, r2, c2; cin >> n >> r1 >> c1 >> r2 >> c2; priority_queue, greater> q; unordered_set s; vector none{}; q.emplace(r1, c1, 0, none); s.insert(to_string(r1) + ',' + to_string(c1)); int m = moves.size(); while (!q.empty()) { auto p = q.top(); for (int i = 0; i < m; i++) { int r = p.r + steps[i][0], c = p.c + steps[i][1]; if (r < 0 || r >= n || c < 0 || c >= n) continue; if (r == r2 && c == c2) { cout << p.d + 1 << endl; for (auto &s : p.path) { cout << s << ' '; } cout << moves[i] << endl; return 0; } if (s.count(to_string(r) + ',' + to_string(c))) continue; auto v = p.path; v.push_back(moves[i]); q.emplace(r, c, p.d + 1, v); s.insert(to_string(r) + ',' + to_string(c)); } q.pop(); } cout << "Impossible" << endl; return 0; }