#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include #include #include #include // Site: www.hackerrank.com // Competition: World Code Sprint 12 // Problem: Red Knight's Shortest Path // Problem Code: Problem 2 // by lboris /* */ typedef unsigned int uint; typedef unsigned long long llu; typedef long long int lls; #define f(i,s,e) for(int i=s;i<(int)(e);++i) #define fe(i,s,e) for(int i=s;i<=(int)(e);++i) typedef unsigned short ushort; typedef std::vector ushvector; typedef std::vector cvector; int X[200][200]; ushort xyp[200][200]; char prv[200][200]; cvector fm[200][200]; struct comp_val { bool operator()(short s1, short s2) const { int x1 = s1 >> 8; int y1 = s1 & 0x0ff; int x2 = s2 >> 8; int y2 = s2 & 0x0ff; if (X[x1][y1] > X[x2][y2]) return true; return false; } }; typedef std::priority_queue xqueue; char * ss[7] = { "","UL","UR","R","LR","LL","L" }; xqueue q; int dx[7] = { 0,-2,-2,0,2,2,0 }; int dy[7] = { 0,-1,1,2,1,-1,-2 }; bool isless(cvector& v1, int lv, cvector& v2) { f(i, 0, v1.size()) { if (v1[i] < v2[i])return true; if (v1[i] > v2[i])return false; } if (lv < v2.back())return true; return false; } int main(int argc, char **argv) { int N; int x1, y1, x2, y2; scanf("%d", &N); scanf("%d %d %d %d", &x1, &y1, &x2, &y2); memset(X, 0x7f, sizeof(X)); memset(xyp, 0, sizeof(xyp)); memset(prv, 0, sizeof(prv)); q.push(x1 << 8 | y1); X[x1][y1] = 0; xyp[x1][y1] = x1 << 8 | y1; prv[x1][y1] = 0; while (!q.empty()) { ushort sh = q.top(); q.pop(); int x = sh >> 8; int y = sh & 0x0ff; int v = X[x][y]; cvector& cv = fm[x][y]; int nx, ny; fe(i, 1, 6) { nx = x + dx[i]; ny = y + dy[i]; if (nx >= 0 && nx= 0 && ny v + 1 || (X[nx][ny] == v + 1 && isless(cv,i,fm[nx][ny]))) { X[nx][ny] = v + 1; prv[nx][ny] = i; xyp[nx][ny] = sh; fm[nx][ny] = fm[x][y]; fm[nx][ny].push_back(i); q.push(nx << 8 | ny); } } } } int dx = X[x2][y2]; if (dx == 0x7f7f7f7f) { printf("Impossible\n"); } else { printf("%d\n", dx); cvector res(dx); int x = x2; int y = y2; int idx = dx - 1; while (x != x1 || y != y1) { int px = xyp[x][y] >> 8; int py = xyp[x][y] & 0x0ff; res[idx--] = prv[x][y]; x = px; y = py; } f(i, 0, dx) { printf("%s%c", ss[res[i]], (i == dx - 1) ? '\n' : ' '); } } return 0; }