#include using namespace std; int shortest_path_num_steps(int i_start, int j_start, int i_end, int j_end) { if ((i_start == i_end) && (j_start == j_end)) return 0; int vert_diff_abs = abs(i_end - i_start); if (vert_diff_abs&1) return -1; int hor_diff_abs = abs(j_end - j_start); int diff_abs = (hor_diff_abs - vert_diff_abs/2); if (diff_abs&1) return -1; int res = vert_diff_abs/2; if (hor_diff_abs <= res) return res; return (hor_diff_abs - res)/2 + res; } void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { if (shortest_path_num_steps(i_start, j_start, i_end, j_end) < 0) { cout << "Impossible" << endl; } else { vector steps = {"UL", "UR", "R", "LR", "LL", "L"}; vector steps_i = {-2, -2, 0, 2, 2, 0}; vector steps_j = {-1, 1, 2, 1, -1, -2}; vector path; while (true) { string shortest_step = ""; int num_steps = -1; int shortest_i, shortest_j; for (int i = 0; i < 6; ++i) { string cur_step = steps[i]; int i_next = i_start + steps_i[i]; int j_next = j_start + steps_j[i]; if ((i_next >= 0) && (i_next < n) && (j_next >= 0) && (j_next < n)) { int cur_num_steps = shortest_path_num_steps(i_next, j_next, i_end, j_end); if (cur_num_steps >= 0) { if ((num_steps < 0) || (cur_num_steps < num_steps)) { num_steps = cur_num_steps; shortest_step = cur_step; shortest_i = steps_i[i]; shortest_j = steps_j[i]; } } } } path.push_back(shortest_step); i_start += shortest_i; j_start += shortest_j; if (num_steps == 0) break; } cout << path.size() << endl; for(int i=0; i> 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; }