#include using namespace std; bool isFound = false; struct cell { int x, y; int dis; int how; cell *prev; //cell() {} //cell(int x, int y, int dis, int how) : x(x), y(y), dis(dis), how(how), prev(prev) {} }; void printSol(cell *asd){ cout<dis< qu; while(asd->prev != 0){ qu.push_back(asd->how); asd=asd->prev; } int i=qu.size()-1; while(i>=0){ switch(qu[i--]){ case 0: cout<<"UL "; break; case 1: cout<<"UR "; break; case 2: cout<<"R "; break; case 3: cout<<"LR "; break; case 4: cout<<"LL "; break; case 5: cout<<"L "; break; } } } bool isInside(int x, int y, int N) { if (x >= 0 && x <= N && y >= 0 && y <= N) return true; return false; } 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. int delta_i[] = {-2, -2, 0, 2, 2, 0}; int delta_j[] = {-1, 1, 2, 1, -1, -2}; queue q; cell * t = new cell; t->x=i_start; t->y=j_start; t->dis = 0; t->how=0; t->prev = 0; q.push(t); int x, y; bool visit[n + 1][n + 1]; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) visit[i][j] = false; visit[i_start][j_start] = true; cell *xyz; while (!q.empty()){ xyz = q.front(); q.pop(); visit[xyz->x][xyz->y] = true; if (xyz->x == i_end && xyz->y == j_end){ isFound = true; printSol(xyz); return; } for (int i = 0; i < 6; i++){ x = xyz->x + delta_i[i]; y = xyz->y + delta_j[i]; //cout<<"-->"<x=x; abc->y=y; abc->dis = xyz->dis + 1; abc->how=i; abc->prev=xyz; q.push(abc); } } } if(!isFound){ cout<<"Impossible"; } } 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+1, i_start, j_start, i_end, j_end); return 0; }