#include #include #include #include using namespace std; #define MAXN 201 #define REP(i, a, b) for(int i = a; i <= b; i++) #define PB push_back #define MP make_pair #define PII pair #define F first #define S second #define pB pop_back int n, is, js, ie, je, dist[MAXN][MAXN], steps=0; vector adj[MAXN][MAXN]; bool vis[MAXN][MAXN], found=false; queue > > q; vector finalpath; bool ingrid(int i, int j) { if ((i >= 0) && (i < n)) {/* do nothing */} else {return false;} if ((j >= 0) && (j < n)) {return true;} else {return false;} } void connect(int i, int j) { if (ingrid(i, j-2)) adj[i][j].PB(MP(i, j-2)); else adj[i][j].PB(MP(-1, -1)); if (ingrid(i+2, j-1)) adj[i][j].PB(MP(i+2, j-1)); else adj[i][j].PB(MP(-1, -1)); if (ingrid(i+2, j+1)) adj[i][j].PB(MP(i+2, j+1)); else adj[i][j].PB(MP(-1, -1)); if (ingrid(i, j+2)) adj[i][j].PB(MP(i, j+2)); else adj[i][j].PB(MP(-1, -1)); if (ingrid(i-2, j+1)) adj[i][j].PB(MP(i-2, j+1)); else adj[i][j].PB(MP(-1, -1)); if (ingrid(i-2, j-1)) adj[i][j].PB(MP(i-2, j-1)); else adj[i][j].PB(MP(-1, -1)); } // void getpath(PII vert) { // if (steps == dist[ie][je]) { // if (vert == MP(ie, je) && !found) {finalpath = path; found = true; return;} // else {return;} // } // for (int i = 5; i >= 0; --i) // { // PII s = adj[vert.F][vert.S][i]; // if (s.F == -1) continue; // if (found) break; // if (dist[vert.F][vert.S]+1 == dist[s.F][s.S]) { // steps++; path.PB(i); // getpath(s); // path.pB(); steps--; // } // } // } void display() { for(auto k: finalpath) { if (k == 0) cout << "L "; else if (k == 1) cout << "LL "; else if (k == 2) cout << "LR "; else if (k == 3) cout << "R "; else if (k == 4) cout << "UR "; else if (k == 5) cout << "UL "; } cout << endl; } int main() { cin >> n >> is >> js >> ie >> je; memset(vis, false, sizeof(vis)); memset(dist, -1, sizeof(dist)); REP(i, 0, n-1) {REP(j, 0, n-1) {connect(i, j);}} vis[is][js] = true; dist[is][js] = 0; q.push(MP(MP(is, js), finalpath)); while(!q.empty()) { PII s = q.front().F; finalpath = q.front().S; q.pop(); if (s == MP(ie, je)) break; for(int i = 5; i >= 0; i--) { PII k = adj[s.F][s.S][i]; if (k.F == -1) continue; if (vis[k.F][k.S]) continue; vis[k.F][k.S] = true; dist[k.F][k.S] = 1 + dist[s.F][s.S]; finalpath.PB(i); q.push(MP(k, finalpath)); finalpath.pB(); } } if (dist[ie][je] == -1) {cout << "Impossible" << endl; return 0;} cout << dist[ie][je] << endl; display(); }