#include using namespace std; enum moves{ UL = 0, UR = 1, R = 2, LR = 3, LL = 4, L = 5 }; int visited[200][200]; int gMin = 99999999999; int minSteps[400]; int steps[400]; void findNextStep(int n, int iCur, int jCur, int iEnd, int jEnd, int curMin) { curMin += 1; // cout << "cur: " << curMin << " " << iCur << " " << jCur << endl; if (iCur == iEnd && jCur == jEnd) { if (curMin < gMin) { gMin = curMin; memcpy(minSteps, steps, gMin * sizeof(int)); // cout << "gMin: " << gMin << endl; // cout << gMin << endl; // for (int i = 0; i < gMin; i++) // { // cout << minSteps[i] << " "; // } // cout << endl; // getchar(); } else { return; } } visited[iCur][jCur] = 1; int iNext = iCur - 2; int jNext = jCur - 1; if (iNext >= 0 && jNext >= 0 && iNext < n && jNext < n) { if (visited[iNext][jNext] == 0) { // cout << "step: 0 "<< curMin <= 0 && jNext >= 0 && iNext < n && jNext < n) { if (visited[iNext][jNext] == 0) { // cout << "step: 1 " << curMin << endl; steps[curMin] = 1; findNextStep(n, iNext, jNext, iEnd, jEnd, curMin); } } iNext = iCur; jNext = jCur + 2; if (iNext >= 0 && jNext >= 0 && iNext < n && jNext < n) { if (visited[iNext][jNext] == 0) { // cout << "step: 2 " << curMin << endl; steps[curMin] = 2; findNextStep(n, iNext, jNext, iEnd, jEnd, curMin); } } iNext = iCur + 2; jNext = jCur + 1; if (iNext >= 0 && jNext >= 0 && iNext < n && jNext < n) { if (visited[iNext][jNext] == 0) { // cout << "step: 3 " << curMin << endl; steps[curMin] = 3; findNextStep(n, iNext, jNext, iEnd, jEnd, curMin); } } iNext = iCur + 2; jNext = jCur - 1; if (iNext >= 0 && jNext >= 0 && iNext < n && jNext < n) { if (visited[iNext][jNext] == 0) { // cout << "step: 4 " << curMin << endl; steps[curMin] = 4; findNextStep(n, iNext, jNext, iEnd, jEnd, curMin); } } iNext = iCur; jNext = jCur - 2; if (iNext >= 0 && jNext >= 0 && iNext < n && jNext < n) { if (visited[iNext][jNext] == 0) { // cout << "step: 5 " << curMin << endl; steps[curMin] = 5; findNextStep(n, iNext, jNext, iEnd, jEnd, curMin); } } visited[iCur][jCur] = 0; } 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 == 1) { cout << "Impossible" << endl; return; } memset(visited, 0, 200*200); findNextStep(n, i_start, j_start, i_end, j_end, -1); // cout << "1" << endl; // cout << "UR" << endl; cout << gMin << endl; for (int i = 0; i < gMin; i++) { switch (minSteps[i]) { case 0: cout << "UL "; break; case 1: cout << "UR "; break; case 2: cout << "R "; break; case 3: cout << "LR "; break; case 4: cout << "LL "; break; case 5: cout << "L "; break; } } cout << endl; // getchar(); } 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; }