#include #include using namespace std; struct xy{ int x; int y; }; 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< vector > g(n, vector(n, false)); vector< vector > p(n, vector(n)); for (int i = 0; i q; xy start; start.y = i_start; start.x = j_start; q.push_back(start); g[start.y][start.x] = true; while (!q.empty()) { const xy& v = q.front(); if (v.y == i_end && v.x == j_end) { //got there break; } if (v.x - 1 >= 0 && v.y - 2 >= 0) { //UL if (!g[v.y - 2][v.x - 1]) { xy w; w.y = v.y - 2; w.x = v.x - 1; q.push_back(w); g[w.y][w.x] = true; p[w.y][w.x] = v; } } if (v.x + 1= 0) { //UR if (!g[v.y - 2][v.x + 1]) { xy w; w.y = v.y - 2; w.x = v.x + 1; q.push_back(w); g[w.y][w.x] = true; p[w.y][w.x] = v; } } if (v.x + 2= 0 && v.y + 2= 0) { //L if (!g[v.y][v.x - 2]) { xy w; w.y = v.y; w.x = v.x - 2; q.push_back(w); g[w.y][w.x] = true; p[w.y][w.x] = v; } } q.pop_front(); } if (g[i_end][j_end]) { vector mvs; int i = i_end; int j = j_end; while (p[i][j].x != -1 && p[i][j].y != -1) { if (j - p[i][j].x == -2 && i - p[i][j].y == 0) { mvs.push_back("L"); } else if (j - p[i][j].x == 2 && i - p[i][j].y == 0) { mvs.push_back("R"); } else if (j - p[i][j].x == -1 && i - p[i][j].y == -2) { mvs.push_back("UL"); } else if (j - p[i][j].x == 1 && i - p[i][j].y == -2) { mvs.push_back("UR"); } else if (j - p[i][j].x == -1 && i - p[i][j].y == 2) { mvs.push_back("LL"); } else if (j - p[i][j].x == 1 && i - p[i][j].y == 2) { mvs.push_back("LR"); } xy w = p[i][j]; i = w.y; j = w.x; } ::std::reverse(mvs.begin(), mvs.end()); cout << mvs.size() << endl; for (const string& mv : mvs) { cout << mv << " "; } cout << endl; } else { cout << "Impossible" << endl; } } 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; }