#include #include #include #include #include #include #include #define IMP { printf("Impossible"); return; } static int moves[6][2] = { {-1, -2}, //UL {1, -2}, //UR {2, 0}, //R {1, 2}, //LR {-1, 2}, //LL {-2, 0}, //L }; static int board[200][200]; static void cost_neighbors(int n, int i, int j, int c) { int m, m_i, m_j; int to_visit[6][2]; int tvc = 0; for (m = 0; m < 6; m++) { m_i = moves[m][1] + i; m_j = moves[m][0] + j; if (m_i >= n || m_j >= n || m_i < 0 || m_j < 0) continue; if (board[m_i][m_j] < c + 1) continue; board[m_i][m_j] = c + 1; to_visit[tvc][1] = m_i; to_visit[tvc][0] = m_j; tvc++; } for (m = 0; m < tvc; m++) { cost_neighbors(n, to_visit[m][1], to_visit[m][0], c + 1); } } void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { int moves_taken[200]; int i = i_start, j = j_start, m, m_i, m_j, c, mt = 0, b, bc; if (((i_start + 1) & 1) ^ (((i_end + 1) & 1))) { IMP; } c = abs(i_start - i_end); if (((j_start + 1) & 1) ^ ((j_end + 1) & 1)) { if (c % 4 != 2) IMP; } else { if (c % 4 != 0) IMP; } for (m_i = 0; m_i < 200; m_i++) { for (m_j = 0; m_j < 200; m_j++) { board[m_i][m_j] = 400; } } board[i_end][j_end] = 0; cost_neighbors(n, i_end, j_end, 0); while (i != i_end || j != j_end) { bc = 400; for (m = 0; m < 6; m++) { m_i = moves[m][1] + i; m_j = moves[m][0] + j; if (m_i >= n || m_j >= n || m_i < 0 || m_j < 0) continue; if (board[m_i][m_j] < bc) { b = m; bc = board[m_i][m_j]; } } i += moves[b][1]; j += moves[b][0]; moves_taken[mt] = b; mt++; } printf("%d\n", mt); for (m = 0; m < mt; m++){ switch(moves_taken[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; default: printf("L "); } } } 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; }