#include #include #include #include #include #include #include void printMove(int m) { switch (m) { case 0: printf("UL "); break; case 1: printf("UR "); break; case 2: printf("R "); break; case 3: printf("LR "); break; case 4: printf("LL "); break; case 5: printf("L"); break; } } 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 numMoves = 0; int listSize = 20; int *movesList; movesList = (int *) malloc(sizeof(int) * listSize); if ((i_start % 2 != i_end % 2) || (i_start % 4 == i_end % 4 && j_start % 2 != j_end % 2) || (i_start % 4 != i_end % 4 && j_start % 2 == j_end % 2)) { printf("Impossible\n"); return; } else { while (i_start != i_end || j_start != j_end) { if (i_end < i_start) { //If end is above i_start--; i_start--; if (j_end <= j_start && j_start > 0) { //If end is to the upper left movesList[numMoves] = 0; j_start--; } else { //If end is to the upper right movesList[numMoves] = 1; j_start++; } } else if (i_end > i_start) { //If end is below i_start++; i_start++; if (j_end >= j_start && j_start < n) { //If end is to the lower right movesList[numMoves] = 3; j_start++; } else { movesList[numMoves] = 4; //If end is to the lower left j_start--; } } else if (j_start < j_end) { //If end is even movesList[numMoves] = 2; j_start++; j_start++; } else { movesList[numMoves] = 5; j_start--; j_start--; } numMoves++; if (numMoves == listSize) { listSize += 10; movesList = (int *) realloc(movesList, sizeof(int) * listSize); } } } printf("%d\n", numMoves); for (int i = 0; i < numMoves; ++i) { printMove(movesList[i]); } printf("\n"); } int main() { int n; scanf("%i", &n); int i_start; int j_start; int i_end; int j_end; scanf("%i %i %i %i", &i_start, &j_start, &i_end, &j_end); printShortestPath(n, i_start, j_start, i_end, j_end); return 0; }