#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 i = i_start; int j = j_start; int i_dist, j_dist; int UL_steps, UR_steps, R_steps, LR_steps, LL_steps, L_steps, min_steps; int numSteps = 0; vector stepSequence; while (abs(i-i_end) > 2 || abs(j-j_end) > 2){ i_dist = i-i_end; j_dist = j-j_end; if (j_dist > 0){ // Only consider options that move left UL_steps = abs(i-2-i_end) + abs(j-1-j_end); LL_steps = abs(i+2-i_end) + abs(j-1-j_end); L_steps = abs(i-i_end) + abs(j-2-j_end); int steps[] = {UL_steps,LL_steps,L_steps}; min_steps = *min_element(steps, steps+3); if (UL_steps == min_steps){ numSteps++; i -= 2; j--; stepSequence.push_back("UL"); } else if (LL_steps == min_steps){ numSteps++; i += 2; j--; stepSequence.push_back("LL"); } else { numSteps++; j -= 2; stepSequence.push_back("L"); } } else if (j_dist < 0){ // Only consider options that move right UR_steps = abs(i-2-i_end) + abs(j+1-j_end); R_steps = abs(i-i_end) + abs(j+2-j_end); LR_steps = abs(i+2-i_end) + abs(j+1-j_end); int steps[] = {UR_steps,R_steps,LR_steps}; min_steps = *min_element(steps, steps+3); if (UR_steps == min_steps){ numSteps++; i -= 2; j++; stepSequence.push_back("UR"); } else if (R_steps == min_steps){ numSteps++; j += 2; stepSequence.push_back("R"); } else { numSteps++; i += 2; j++; stepSequence.push_back("LR"); } } else { // Not necessary to consider just left/right movements for positions directly up or down UL_steps = abs(i-2-i_end) + abs(j-1-j_end); UR_steps = abs(i-2-i_end) + abs(j+1-j_end); LR_steps = abs(i+2-i_end) + abs(j+1-j_end); LL_steps = abs(i+2-i_end) + abs(j-1-j_end); int steps[] = {UL_steps,UR_steps,LR_steps,LL_steps}; min_steps = *min_element(steps, steps+4); if (UL_steps == min_steps){ numSteps++; i -= 2; j--; stepSequence.push_back("UL"); } else if (UR_steps == min_steps){ numSteps++; i -= 2; j++; stepSequence.push_back("UR"); } else if (LR_steps == min_steps){ numSteps++; i += 2; j++; stepSequence.push_back("LR"); } else { numSteps++; i += 2; j--; stepSequence.push_back("LL"); } } } i_dist = i-i_end; j_dist = j-j_end; if (i_dist == -2 && j_dist == -1){ numSteps++; stepSequence.push_back("LR"); cout << numSteps << endl; for (int k = 0; k < stepSequence.size(); k++){ cout << stepSequence[k] << " "; } } else if (i_dist == -2 && j_dist == 1){ numSteps++; stepSequence.push_back("LL"); cout << numSteps << endl; for (int k = 0; k < stepSequence.size(); k++){ cout << stepSequence[k] << " "; } } else if (i_dist == 0 && j_dist == 2){ numSteps++; stepSequence.push_back("L"); cout << numSteps << endl; for (int k = 0; k < stepSequence.size(); k++){ cout << stepSequence[k] << " "; } } else if (i_dist == 2 && j_dist == 1){ numSteps++; stepSequence.push_back("UL"); cout << numSteps << endl; for (int k = 0; k < stepSequence.size(); k++){ cout << stepSequence[k] << " "; } } else if (i_dist == 2 && j_dist == -1){ numSteps++; stepSequence.push_back("UR"); cout << numSteps << endl; for (int k = 0; k < stepSequence.size(); k++){ cout << stepSequence[k] << " "; } } else if (i_dist == 0 && j_dist == -2){ numSteps++; stepSequence.push_back("R"); cout << numSteps << endl; for (int k = 0; k < stepSequence.size(); k++){ cout << stepSequence[k] << " "; } } else { cout << "Impossible" << endl; } 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; }