#include using namespace std; struct Node { int x, y, step; vector path; Node(int a, int b, int c, vector & d) : x(a), y(b), step(c), path(d) {} }; void genResult(vector & ans, vector & path, string & lastMove) { if(ans.empty()) { ans = path; ans.push_back(lastMove); return ; } // UL, UR, R, LR, LL, L unordered_map um; um["UL"] = 0; um["UR"] = 1; um["R"] = 2; um["LR"] = 3; um["LL"] = 4; um["L"] = 5; for(int i = 0; i < path.size(); i ++) { int a = um[ans[i]]; int b = um[path[i]]; if(a < b) return ; else if(a > b) { ans = path; ans.push_back(lastMove); return ; } } int a = um[ans[ans.size()-1]]; int b = um[lastMove]; if(a < b) return ; ans[ans.size()-1] = lastMove; } 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 vn[2]; vector< vector > flag(n, vector(n, false)); int cur = 0; int move[][2] = { {-2, -1}, {-2, 1}, {0, 2}, {2, 1}, {2, -1}, {0, -2} }; string movePath[] = { "UL", "UR", "R", "LR", "LL", "L" }; vector ans; vn[cur].push_back(Node(i_start, j_start, 0, ans)); flag[i_start][j_start] = true; while(!vn[cur].empty()) { int next = !cur; int minStep = -1; vn[next].clear(); for(int i = 0; i < vn[cur].size(); i ++) { Node & node = vn[cur][i]; for(int j = 0; j < 6; j ++) { int nx = node.x + move[j][0]; int ny = node.y + move[j][1]; if(nx < 0 || nx >= n || ny < 0 || ny >= n || flag[nx][ny]) continue; if(nx == i_end && ny == j_end) { minStep = node.step + 1; genResult(ans, node.path, movePath[j]); } else { Node nextNode(nx, ny, node.step + 1, node.path); nextNode.path.push_back(movePath[j]); vn[next].push_back(nextNode); flag[nx][ny] = true; } } } if(-1 != minStep) { cout << minStep << endl; for(int i = 0; i < ans.size(); i ++) { cout << ans[i]; if(i != ans.size() - 1) cout << " "; else cout << endl; } return ; } cur = next; } cout << "Impossible" << endl; } int main() { int n = 0; cin >> n; int i_start = 0; int j_start = 0; int i_end = 0; int j_end = 0; cin >> i_start >> j_start >> i_end >> j_end; printShortestPath(n, i_start, j_start, i_end, j_end); return 0; }