#include using namespace std; int getDist(int i_start, int j_start, int i_end, int j_end) { int di = i_end - i_start; if (di <0) di *= -1; int dj = j_end - j_start; if (dj <0) dj *= -1; int vert = di/2; int hor = dj; if (hor >= vert) { hor -= vert; } else { hor = 0; } hor /= 2; int moves = vert + hor; return moves; } bool isValid(int n, int i_curr, int j_curr) { return 0 <= i_curr && i_curr < n && 0 <= j_curr && j_curr < n; } void buildPath(int n, int i_start, int j_start, int i_end, int j_end) { int dist = getDist(i_start, j_start, i_end, j_end); if (dist == 0) { return; } const int MAX = 40002; int min = MAX; string minMove; int i_aux, j_aux, i_min, j_min; //UL i_aux = i_start - 2; j_aux = j_start - 1; if (isValid(n,i_aux,j_aux)) { int d = getDist(i_aux,j_aux,i_end,j_end); if (min > d) { min = d; minMove = "UL"; i_min = i_aux; j_min = j_aux; } } //UR i_aux = i_start - 2; j_aux = j_start + 1; if (isValid(n,i_aux,j_aux)) { int d = getDist(i_aux,j_aux,i_end,j_end); if (min > d) { min = d; minMove = "UR"; i_min = i_aux; j_min = j_aux; } } //R i_aux = i_start; j_aux = j_start + 2; if (isValid(n,i_aux,j_aux)) { int d = getDist(i_aux,j_aux,i_end,j_end); if (min > d) { min = d; minMove = "R"; i_min = i_aux; j_min = j_aux; } } //LR i_aux = i_start+2; j_aux = j_start + 1; if (isValid(n,i_aux,j_aux)) { int d = getDist(i_aux,j_aux,i_end,j_end); if (min > d) { min = d; minMove = "LR"; i_min = i_aux; j_min = j_aux; } } //LL i_aux = i_start+2; j_aux = j_start - 1; if (isValid(n,i_aux,j_aux)) { int d = getDist(i_aux,j_aux,i_end,j_end); if (min > d) { min = d; minMove = "LL"; i_min = i_aux; j_min = j_aux; } } //L i_aux = i_start; j_aux = j_start - 2; if (isValid(n,i_aux,j_aux)) { int d = getDist(i_aux,j_aux,i_end,j_end); if (min > d) { min = d; minMove = "L"; i_min = i_aux; j_min = j_aux; } } cout << minMove << " "; buildPath(n, i_min, j_min, i_end, j_end); } 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 di = i_end - i_start; if (di < 0) di *= -1; int dj = j_end - j_start; if (dj < 0) dj *= -1; if (di % 2 != 0) { cout << "Impossible" << endl; return; } if (di % 4 == 0 && (dj % 2) != 0) { cout << "Impossible" << endl; return; } if (di % 4 == 2 && (dj % 2) == 0) { cout << "Impossible" << endl; return; } int vert = di/2; int hor = dj; if (hor >= vert) { hor -= vert; } else { hor = 0; } hor /= 2; int moves = vert + hor; cout << moves << endl; buildPath(n,i_start,j_start,i_end,j_end); 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; }