#include using namespace std; std::vector output; void printPath(int n, int i_start, int j_start, int i_end, int j_end) { if(i_start == i_end){ if(j_start == j_end){ return; } if(j_start < j_end){ output.push_back("R "); printPath(n, i_start, j_start + 2, i_end, j_end); return; } if(j_start > j_end){ output.push_back("L "); printPath(n, i_start, j_start - 2, i_end, j_end); return; } } if(i_start < i_end){ if(j_start == j_end){ int c = (i_end - i_start) / 4; while(c && ((j_start + 1) < n)){ output.push_back("LR "); i_start += 2; j_start += 1; c--; } printPath(n, i_start, j_start, i_end, j_end); /* if((j_start + 1) < n){ output.push_back("LR "); printPath(n, i_start + 2, j_start + 1, i_end, j_end); } else{ output.push_back("LL "); printPath(n, i_start + 2, j_start - 1, i_end, j_end); } */ return; } if(j_start < j_end){ output.push_back("LR "); printPath(n, i_start + 2, j_start + 1, i_end, j_end); return; } if(j_start > j_end){ output.push_back("LL "); printPath(n, i_start + 2, j_start - 1, i_end, j_end); return; } } if(i_start > i_end){ if(j_start == j_end){ int c = (i_start - i_end) / 4; while(c && ((j_start - 1) >= 0)){ output.push_back("UL "); i_start -= 2; j_start -= 1; c--; } printPath(n, i_start, j_start, i_end, j_end); /* if((j_start - 1) >= 0){ output.push_back("UL "); printPath(n, i_start - 2 , j_start - 1, i_end, j_end); } else{ output.push_back("UR "); printPath(n, i_start - 2, j_start + 1, i_end, j_end); } */ return; } if(j_start < j_end){ output.push_back("UR "); printPath(n, i_start - 2, j_start + 1, i_end, j_end); return; } if(j_start > j_end){ output.push_back("UL "); printPath(n, i_start - 2 , j_start - 1, i_end, j_end); return; } } } 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. if((i_start - i_end) % 2 != 0){ cout << "Impossible"; return; } int temp = (i_start - i_end) / 2; if((j_start - j_end) % 2 == 1 && temp % 2 == 0){ cout << "Impossible"; return; } if((j_start - j_end) % 2 == 0 && temp % 2 == 1){ cout << "Impossible"; return; } printPath(n, i_start, j_start, i_end, j_end); cout << output.size() << endl; for(int i = 0; i < output.size(); i++){ cout << output[i]; } } 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; }