#define problem "Red Knight's Shortest Path" #include #define Z (1 - 1) #define fi first #define se second using namespace std; const int maxN = 2e2 + 11; typedef pair ii; const ii p[6] = {{-2, -1}, {-2, 1}, {Z, 2}, {2, 1}, {2, -1}, {Z, -2}}; const string s[6] = {"UL", "UR", "R", "LR", "LL", "L"}; int N; ii P[maxN][maxN]; int xs, ys, xe, ye; void trace(ii v, ii S, int leng){ if(v == S){ cout << leng << '\n'; return; } trace(P[v.fi][v.se], S, leng + 1); for(int i = Z; i < 6; i++) if(ii(P[v.fi][v.se].fi + p[i].fi, P[v.fi][v.se].se + p[i].se) == v){ cout << s[i] << ' '; break; } } int main(){ cin >> N; cin >> xs >> ys >> xe >> ye; queue bfs_node; bfs_node.push(ii(xs, ys)); P[xs][ys] = ii(-1, -1); while(!bfs_node.empty()){ ii u = bfs_node.front(); bfs_node.pop(); for(int i = Z; i < 6; i++){ ii v(u.fi + p[i].fi, u.se + p[i].se); if(v.fi < Z || v.se < Z || v.fi >= N || v.se >= N) continue; if(P[v.fi][v.se] != ii(Z, Z)) continue; P[v.fi][v.se] = u; bfs_node.push(v); } } if(P[xe][ye] == ii(Z, Z)){ cout << "Impossible"; return Z; } trace(ii(xe, ye), ii(xs, ys), Z); }