#include #include using namespace std; int l; int mini ; int *p; int *tp ; void check(int n, int x1, int y1, int x2, int y2) ; 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. check(n, i_start, j_start, i_end, j_end); if(mini==n) { cout << "Impossible" << endl ; return ; } cout << mini << endl ; for (int i = 0; i <= mini; ++i) { switch(tp[i]) { case 1 : cout << "UL " ; break ; case 2 : cout << "UR " ; break ; case 3 : cout << "R " ; break ; case 4 : cout << "LR " ; break ; case 5 : cout << "LL " ; break ; case 6 : cout << "L " ; break ; } } cout << endl ; } void check(int n, int x1, int y1, int x2, int y2) { //cout << "in" << endl ; if(l>mini) return ; if(x1 == x2 && y1 == y2) { //cout << "in" << endl; if(l < mini) { for (int i = 0; i <= l; ++i) { tp[i] = p[i]; } mini = l ; //cout << "kk l " << l << endl ; return ; } } else if (x1 > n || y1 > n || x1 < 0 || y1 < 0) return ; p[l++] = 1 ; check(n,x1-2, y1-1, x2, y2); p[l--] = '\0' ; p[l++] = 2 ; check(n,x1-2, y1+1, x2, y2); p[l--] = '\0' ; p[l++] = 3 ; check(n,x1, y1+2, x2, y2); p[l--] = '\0' ; p[l++] = 4 ; check(n,x1+2, y1+1, x2, y2); p[l--] = '\0' ; p[l++] = 5 ; check(n,x1+2, y1-1, x2, y2); p[l--] = '\0' ; p[l++] = 6 ; check(n,x1, y1-2, x2, y2); p[l--] = '\0' ; } 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; p = (int *)malloc(sizeof(int)*n); mini = n ; tp = (int *)malloc(sizeof(int)*n); printShortestPath(n, i_start, j_start, i_end, j_end); return 0; }