#include #include #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 count = 0; vector moves; // if vertical distance is even if (abs(i_start - i_end) % 2 == 0) { // if horizontal distance (once on the same row) is even if (abs(j_start - (abs(i_start - i_end)/2) - j_end) % 2 == 0) { // priority is UL/UR/R/LR/LL/L // special case: start col is same as end col if (j_start == j_end) { // if end is above start if (i_start > i_end) { // bounds checking if (j_start - 1 < 0) { cout << "Impossible" << endl; return; } else j_start -= 1; if (i_start - 2 < 0) { cout << "Impossible" << endl; return; } else i_start -= 2; count++; moves.push_back("UL"); } // if end is below start if (i_end > i_start) { if (j_start + 1 >= n) { cout << "Impossible" << endl; return; } else j_start += 1; if (i_start + 2 >= n) { cout << "Impossible" << endl; return; } else i_start += 2; count++; moves.push_back("LR"); } } // if we need to move up if (i_start > i_end) { // if end position is to the left start position if (j_end < j_start) { while (i_start != i_end) { // bounds checking if (j_start - 1 < 0) { cout << "Impossible" << endl; return; } else j_start -= 1; if (i_start - 2 < 0) { cout << "Impossible" << endl; return; } else i_start -= 2; count++; moves.push_back("UL"); } } // if start position is to the left of the end position if (j_start < j_end) { while (i_start != i_end) { if (j_start + 1 >= n) { cout << "Impossible" << endl; return; } else j_start += 1; if (i_start - 2 < 0) { cout << "Impossible" << endl; return; } else i_start -= 2; count++; moves.push_back("UR"); } } } int vert = (abs(j_start - abs(i_start - i_end) - j_end)) / 2; // if we need to move right if (j_start < j_end) { for (int i = 0; i < vert; i++) { if (j_start + 2 >= n) { cout << "Impossible" << endl; return; } else j_start += 2; count++; moves.push_back("R"); } } // if we need to move down if (i_start < i_end) { // if start position is to the left of the end position if (j_start < j_end) { while (i_start != i_end) { if (j_start + 1 >= n) { cout << "Impossible" << endl; return; } else j_start += 1; if (i_start + 2 >= n) { cout << "Impossible" << endl; return; } else i_start += 2; count++; moves.push_back("LR"); } } // if end position is to the left start position if (j_end < j_start) { while (i_start != i_end) { // bounds checking if (j_start - 1 < 0) { cout << "Impossible" << endl; return; } else j_start -= 1; if (i_start + 2 >= n) { cout << "Impossible" << endl; return; } else i_start += 2; count++; moves.push_back("LL"); } } } // if we need to move left if (j_start > j_end) { for (int i = 0; i < vert; i++) { if (j_start - 2 < 0) { cout << "Impossible" << endl; return; } else j_start -= 2; count++; moves.push_back("L"); } } } else { cout << "Impossible" << endl; return; } } else { cout << "Impossible" << endl; return; } cout << count << endl; for (vector::iterator it = moves.begin(); it != moves.end(); ++it) { if (it + 1 != moves.end()) { cout << *it << " "; } else { cout << *it; } } cout << 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; }