#include #include #include #include #include #include #include #define MAXVAL 1000000 char visited[200][200]; int min_steps[200][200]; char path[40000]; char opt_path[40000]; int go(int n, int i_start, int j_start, int i_end, int j_end, int steps) { // printf("go %d %d %d X%d\n", steps, i_start, j_start, path[steps - 1]); if (i_start < 0 || i_start > n-1) return MAXVAL; if (j_start < 0 || j_start > n-1) return MAXVAL; if (visited[i_start][j_start]) return MAXVAL; if (min_steps[i_start][j_start] <= steps && min_steps[i_start][j_start] != 0) return MAXVAL; min_steps[i_start][j_start] = steps; if (i_start == i_end && j_start == j_end) { for (int i = 0; i < steps; i++) { opt_path[i] = path[i]; // printf("X%d", path[i]); } // printf("\n"); return steps; } visited[i_start][j_start] = 1; int min = MAXVAL; int v = MAXVAL; path[steps] = 0; v = go(n, i_start - 2, j_start - 1, i_end, j_end, steps + 1); if (v < min) { min = v; } path[steps] = 1; v = go(n, i_start - 2, j_start + 1, i_end, j_end, steps + 1); if (v < min) { min = v; } path[steps] = 2; v = go(n, i_start, j_start + 2, i_end, j_end, steps + 1); if (v < min) { min = v; } path[steps] = 3; v = go(n, i_start + 2, j_start + 1, i_end, j_end, steps + 1); if (v < min) { min = v; } path[steps] = 4; v = go(n, i_start + 2, j_start - 1, i_end, j_end, steps + 1); if (v < min) { min = v; } path[steps] = 5; v = go(n, i_start, j_start - 2, i_end, j_end, steps + 1); if (v < min) { min = v; } visited[i_start][j_start] = 0; // printf("M %d %d\n", steps, min); return min; } char *step_strs[] = {"UL", "UR", "R", "LR", "LL", "L"}; 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 min_steps = go(n, i_start, j_start, i_end, j_end, 0); if (min_steps == MAXVAL) { printf("Impossible\n"); } else { printf("%d\n", min_steps); for (int i = 0; i < min_steps; i++) { printf("%s ", step_strs[opt_path[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; }