#include #define mp make_pair #define fi first #define se second using namespace std; int dist[205][205]; int parent[205][205]; bool isValid(int n, int i, int j) { return dist[i][j] == -1 && i >= 0 && j >= 0 && i < n && j < n; } int dr[] = {-2, -2, 0, 2, 2, 0}; int dc[] = {-1, 1, 2, 1, -1, -2}; string ds[] = {"UL", "UR", "R", "LR", "LL", "L"}; void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { memset(dist, -1, sizeof(dist)); queue > q; dist[i_start][j_start] = 0; q.push(mp(i_start, j_start)); while (!q.empty()) { pair now = q.front(); q.pop(); for (int i = 0; i < 6; i++) { int i_next = now.fi + dr[i]; int j_next = now.se + dc[i]; if (isValid(n, i_next, j_next)) { q.push(mp(i_next, j_next)); parent[i_next][j_next] = i; dist[i_next][j_next] = dist[now.fi][now.se] + 1; } } } if (dist[i_end][j_end] == -1) { cout << "Impossible\n"; return; } cout << dist[i_end][j_end] << "\n"; stack path; while (i_end != i_start || j_end != j_start) { int par = parent[i_end][j_end]; path.push(par); i_end -= dr[par]; j_end -= dc[par]; } if (!path.empty()) { cout << ds[path.top()]; path.pop(); while (!path.empty()) { cout << " "; cout << ds[path.top()]; path.pop(); } } } 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; }