#include #include #include using namespace std; 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 deltax, deltay; int moves; bool factible = false; bool solved = false; string path = ""; deltay = i_end - i_start; deltax = j_end - j_start; int aux_i, aux_j; int cur_i, cur_j; int curd_i, curd_j; int odd_i, odd_j; cur_i = i_start; cur_j = j_start; aux_i = i_start; aux_j = j_start; int cur_min_index; string cur_move = ""; moves=0; while((factible || solved)==false) { //first possibility: aux_i = cur_i - 2; aux_j = cur_j - 1; cur_min_index = 1; curd_i = i_end - aux_i; curd_j = j_end - aux_j; //second possibility: aux_i = cur_i - 2; aux_j = cur_j + 1; if(((i_end - aux_i)*(i_end - aux_i)+(j_end - aux_j)*(j_end - aux_j))<((curd_i)*(curd_i)+(curd_j)*(curd_j))) { curd_i = i_end - aux_i; curd_j = j_end - aux_j; cur_min_index = 2; } //third possibility: aux_i = cur_i + 0; aux_j = cur_j + 2; if(((i_end - aux_i)*(i_end - aux_i)+(j_end - aux_j)*(j_end - aux_j))<((curd_i)*(curd_i)+(curd_j)*(curd_j))) { curd_i = i_end - aux_i; curd_j = j_end - aux_j; cur_min_index = 3; } //fourth possibility: aux_i = cur_i + 2; aux_j = cur_j + 1; if(((i_end - aux_i)*(i_end - aux_i)+(j_end - aux_j)*(j_end - aux_j))<((curd_i)*(curd_i)+(curd_j)*(curd_j))) { curd_i = i_end - aux_i; curd_j = j_end - aux_j; cur_min_index = 4; } //fifth possibility: aux_i = cur_i + 2; aux_j = cur_j - 1; if(((i_end - aux_i)*(i_end - aux_i)+(j_end - aux_j)*(j_end - aux_j))<((curd_i)*(curd_i)+(curd_j)*(curd_j))) { curd_i = i_end - aux_i; curd_j = j_end - aux_j; cur_min_index = 5; } //sixth possibility: aux_i = cur_i + 0; aux_j = cur_j - 2; if(((i_end - aux_i)*(i_end - aux_i)+(j_end - aux_j)*(j_end - aux_j))<((curd_i)*(curd_i)+(curd_j)*(curd_j))) { curd_i = i_end - aux_i; curd_j = j_end - aux_j; cur_min_index = 6; } moves +=1; switch(cur_min_index) { case 1: cur_i = cur_i - 2; cur_j = cur_j - 1; cur_move = "UL"; break; case 2: cur_i = cur_i - 2; cur_j = cur_j + 1; cur_move = "UR"; break; case 3: cur_i = cur_i + 0; cur_j = cur_j + 2; cur_move = "R"; break; case 4: cur_i = cur_i + 2; cur_j = cur_j + 1; cur_move = "LR"; break; case 5: cur_i = cur_i + 2; cur_j = cur_j - 1; cur_move = "LL"; break; case 6: cur_i = cur_i + 0; cur_j = cur_j - 2; cur_move = "L"; break; } if(cur_i >= n) { solved=true; } if(cur_j >= n) { solved=true; } if(!solved) { odd_i = (i_end - cur_i) % 2; if(odd_i==1) { solved = true; } if(i_end==cur_i) { odd_j = (j_end - cur_j) % 2; if(odd_j==1) { solved = true; } } if((i_end==cur_i) && (j_end==cur_j)) { factible=true; solved=true; } } stringstream outt; outt << cur_move; if(!solved) { outt << " "; } path = path + outt.str(); } if(factible==true) { cout << moves << endl; cout << path << 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; }