#include using namespace std; typedef struct Pos { int x; int y; } Pos; class Move { public: Move(int x, int y) { p.x = x; p.y = y; len = 0; } string prev; int len; Pos p; }; inline bool isFound(Move* m, int& x, int& y) { return (m->p.x == x && m->p.y == y); } inline bool isValid(Move* m, int& n, int xAdj, int yAdj, vector>& pv) { int newX = (m->p.x + xAdj); int newY = (m->p.y + yAdj); return (newX >= 0) && (newX < n) && (newY >= 0) && (newY < n) && !pv[newX][newY]; } void checkMove(bool& found, Move*& cn, int& n, int xAdj, int yAdj, string s, queue& q, vector>& visited, int x, int y) { if (!found && isValid(cn, n, xAdj, yAdj, visited)) { Move* nextMove = new Move(cn->p.x + xAdj, cn->p.y + yAdj); //cout << "visiting " << s << " from " << cn->p.x << "," << cn->p.y << " = " << nextMove->p.x << ", " << nextMove->p.y << endl; visited[nextMove->p.x][nextMove->p.y] = true; nextMove->prev = cn->prev; nextMove->len = cn->len; if (nextMove->len > 0) { nextMove->prev.append(" "); } nextMove->prev.append(s); nextMove->len += 1; if (isFound(nextMove, x, y)) { cn = nextMove; found = true; } else { q.push(nextMove); } } } void printShortestPath(int n, int y_start, int x_start, int ye, int xe) { Move* cn = new Move(x_start, y_start); vector> visited(n, vector(n)); visited[x_start][y_start] = true; queue q; q.push(cn); bool found = false; while (!q.empty() && !found) { // UL, UR, R, LR, LL, L cn = q.front(); q.pop(); if (isFound(cn, xe, ye)) { found = true; } else { // UL checkMove(found, cn, n, -1, -2, "UL", q, visited, xe, ye); // UR checkMove(found, cn, n, 1, -2, "UR", q, visited, xe, ye); // R checkMove(found, cn, n, 2, 0, "R", q, visited, xe, ye); // LR checkMove(found, cn, n, 1, 2, "LR", q, visited, xe, ye); // LL checkMove(found, cn, n, -1, 2, "LL", q, visited, xe, ye); // L checkMove(found, cn, n, -2, 0, "L", q, visited, xe, ye); } } if (!found) { cout << "Impossible"; } else { // Print the distance along with the sequence of moves. cout << cn->len << endl; cout << cn->prev; } } 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; }