#include #define GRDLEN 200 #define MOVCNT (GRDLEN * GRDLEN) #define STKLEN (GRDLEN * GRDLEN) enum { NOMOVE, UPPER_LEFT, UPPER_RIGHT, RIGHT, LOWER_RIGHT, LOWER_LEFT, LEFT, UNUSED }; int gl, sr, sc, fr, fc, mn, mv[MOVCNT]; void read(void) { scanf("%d", &gl); scanf("%d %d %d %d", &sr, &sc, &fr, &fc); } void exec(void) { static int gm[GRDLEN][GRDLEN]; static int q0[STKLEN][2], q1[STKLEN][2]; static int md[][2] = { {0, 0}, {-2, -1}, {-2, +1}, {0, +2}, {+2, +1}, {+2, -1}, {0, -2} }; int (*qr)[STKLEN][2], (*qw)[STKLEN][2], (*qt)[STKLEN][2]; int lr, lw, r0, c0, r, c, q, m, n, t; for (r = 0; r < gl; ++r) for (c = 0; c < gl; ++c) gm[r][c] = UNUSED; qr = &q0, qw = &q1, lr = lw = 0; (*qr)[lr][0] = sr, (*qr)[lr++][1] = sc, gm[sr][sc] = NOMOVE; while (lr > 0) { for (lw = 0, q = 0; q < lr; ++q) { r0 = (*qr)[q][0], c0 = (*qr)[q][1]; for (m = UPPER_LEFT; m <= LEFT; ++m) { r = r0 + md[m][0], c = c0 + md[m][1]; if (r >= 0 && r < gl && c >= 0 && c < gl && gm[r][c] == UNUSED) gm[r][c] = m, (*qw)[lw][0] = r, (*qw)[lw++][1] = c; } } if (gm[fr][fc] != UNUSED) { for (r = fr, c = fc, mn = 0; gm[r][c] != NOMOVE; ++mn) m = gm[r][c], mv[mn] = m, r -= md[m][0], c -= md[m][1]; for (m = 0, n = mn - 1; m < n; ++m, --n) t = mv[m], mv[m] = mv[n], mv[n] = t; return; } qt = qw, qw = qr, qr = qt, lr = lw; } mn = -1; } void print(void) { char *ms[7] = { "NO", "UL", "UR", "R", "LR", "LL", "L" }; int m; if (mn >= 0) { printf("%d\n", mn); for (m = 0; m < mn; ++m) printf("%s%c", ms[mv[m]], m < mn - 1 ? ' ' : '\n'); } else printf("Impossible\n"); } void repl(void) { read(), exec(), print(); } int main(void) { repl(); return 0; }