#include #include #include #include #include #include using namespace std; int n; enum dir { UL, UR, R, LR, LL, L, NA }; typedef struct point { int x; int y; vector path; point(int px, int py) { x = px; y = py; } } point; queue q; void printresult(const vector& path) { cout << path.size() << endl; for(int i = 0; i < path.size(); i++) { //cout << path[i] << " "; switch(path[i]) { case 0: cout << "UL "; break; case 1: cout << "UR "; break; case 2: cout << "R "; break; case 3: cout << "LR "; break; case 4: cout << "LL "; break; case 5: cout << "L "; default: break; } } } void findpath(int sx, int sy, int ex, int ey, vector< vector >& visited) { q.push(point(sx, sy)); visited[sx][sy] = 1; while(!q.empty()) { point p = q.front(); q.pop(); if(p.x == ex && p.y == ey) { printresult(p.path); return; } if( (p.x > 1) && (p.y > 0) && (visited[p.x - 2][p.y - 1] == 0) ) { point ul = point(p.x - 2, p.y - 1); ul.path = p.path; ul.path.push_back(UL); visited[ul.x][ul.y] = 1; q.push(ul); } if( (p.x > 1) && (p.y < n-1) && (visited[p.x - 2][p.y + 1] == 0) ) { point ur = point(p.x - 2, p.y + 1); ur.path = p.path; ur.path.push_back(UR); visited[ur.x][ur.y] = 1; q.push(ur); } if( (p.y < n-2) && (visited[p.x][p.y + 2] == 0) ) { point r = point(p.x, p.y + 2); r.path = p.path; r.path.push_back(R); visited[r.x][r.y] = 1; q.push(r); } if( (p.x < n-2) && (p.y < n-1) && (visited[p.x + 2][p.y + 1] == 0) ) { point lr = point(p.x + 2, p.y + 1); lr.path = p.path; lr.path.push_back(LR); visited[lr.x][lr.y] = 1; q.push(lr); } if( (p.x < n-2) && (p.y > 0) && (visited[p.x + 2][p.y - 1] == 0) ) { point ll = point(p.x + 2, p.y - 1); ll.path = p.path; ll.path.push_back(LL); visited[ll.x][ll.y] = 1; q.push(ll); } if( (p.y > 1) && (visited[p.x][p.y - 2] == 0) ) { point l = point(p.x, p.y - 2); l.path = p.path; l.path.push_back(L); visited[l.x][l.y] = 1; q.push(l); } } cout << "Impossible" << endl; return; } int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ cin >> n; int sx, sy, ex, ey; cin >> sx >> sy >> ex >> ey; vector initpath; vector< vector > visited(n); for(int i = 0; i < n; i++) { visited[i].resize(n, 0); } findpath(sx, sy, ex, ey, visited); return 0; }