#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define pii pair using namespace std; struct Task { int idx, idy; vector records; }; vector clone(vector &a, string next) { vector res(a); res.push_back(next); return res; } bool bfs(int startIdx, int startIdy, int endIdx, int endIdy, int n) { set visited; list tasks; Task startTask; startTask.idx = startIdx; startTask.idy = startIdy; vector records; startTask.records = records; tasks.push_back(startTask); visited.insert(pii(startIdx, startIdy)); while (!tasks.empty()) { Task currentTask = tasks.front(); tasks.pop_front(); if (currentTask.idx == endIdx && currentTask.idy == endIdy) { cout << currentTask.records.size() << endl; for (int i = 0; i < (int)currentTask.records.size(); i++) { cout << currentTask.records[i] << ' '; } cout << endl; return true; } // UL if (currentTask.idx - 2 >= 0 && currentTask.idy - 1 >= 0) { Task nextTask; nextTask.idx = currentTask.idx - 2; nextTask.idy = currentTask.idy - 1; if (visited.find(pii(nextTask.idx, nextTask.idy)) == visited.end()) { nextTask.records = clone(currentTask.records, "UL"); tasks.push_back(nextTask); visited.insert(pii(nextTask.idx, nextTask.idy)); } } // UR if (currentTask.idx - 2 >= 0 && currentTask.idy + 1 < n) { Task nextTask; nextTask.idx = currentTask.idx - 2; nextTask.idy = currentTask.idy + 1; if (visited.find(pii(nextTask.idx, nextTask.idy)) == visited.end()) { nextTask.records = clone(currentTask.records, "UR"); tasks.push_back(nextTask); visited.insert(pii(nextTask.idx, nextTask.idy)); } } // R if (currentTask.idy + 2 < n) { Task nextTask; nextTask.idx = currentTask.idx; nextTask.idy = currentTask.idy + 2; if (visited.find(pii(nextTask.idx, nextTask.idy)) == visited.end()) { nextTask.records = clone(currentTask.records, "R"); tasks.push_back(nextTask); visited.insert(pii(nextTask.idx, nextTask.idy)); } } // LR if (currentTask.idx + 2 < n && currentTask.idy + 1 < n) { Task nextTask; nextTask.idx = currentTask.idx + 2; nextTask.idy = currentTask.idy + 1; if (visited.find(pii(nextTask.idx, nextTask.idy)) == visited.end()) { nextTask.records = clone(currentTask.records, "LR"); tasks.push_back(nextTask); visited.insert(pii(nextTask.idx, nextTask.idy)); } } // LL if (currentTask.idx + 2 < n && currentTask.idy - 1 >= 0) { Task nextTask; nextTask.idx = currentTask.idx + 2; nextTask.idy = currentTask.idy - 1; if (visited.find(pii(nextTask.idx, nextTask.idy)) == visited.end()) { nextTask.records = clone(currentTask.records, "LL"); tasks.push_back(nextTask); visited.insert(pii(nextTask.idx, nextTask.idy)); } } // L if (currentTask.idy - 2 >= 0) { Task nextTask; nextTask.idx = currentTask.idx; nextTask.idy = currentTask.idy - 2; if (visited.find(pii(nextTask.idx, nextTask.idy)) == visited.end()) { nextTask.records = clone(currentTask.records, "L"); tasks.push_back(nextTask); visited.insert(pii(nextTask.idx, nextTask.idy)); } } } return false; } int main() { ios::sync_with_stdio(false); int n; cin >> n; int startIdx, startIdy, endIdx, endIdy; cin >> startIdx >> startIdy >> endIdx >> endIdy; if(!bfs(startIdx, startIdy, endIdx, endIdy, n)) { cout << "Impossible" << endl; } return 0; }