#include #include #include #include #include #include #include using namespace std; typedef struct { bool visited; int sh; int px; int py; int d; }grid; string ord[6] = {"UL", "UR", "R", "LR", "LL", "L"}; pair shift[6]; queue > v; bool is_safe(int n, int x, int y); int main() { shift[0] = make_pair(-2, -1); shift[1] = make_pair(-2, 1); shift[2] = make_pair(0, 2); shift[3] = make_pair(2, 1); shift[4] = make_pair(2, -1); shift[5] = make_pair(0, -2); int n; cin >> n; grid **a = new grid*[n]; for(int i = 0; i < n; i++) { a[i] = new grid[n]; for(int j = 0; j < n; j++) { a[i][j].visited = false; //a[i][j].sh = a[i][j].px = a[i][j].py = -1; } } int is, js, ie, je; cin >> is >> js >> ie >> je; a[is][js].visited = true; a[is][js].sh = a[is][js].px = a[is][js].py = -1; a[is][js].d = 0; v.push(make_pair(is,js)); int x,y; bool flag = false; while(!v.empty()) { x = v.front().first; y = v.front().second; //cout << x << " " << y << endl; v.pop(); for(int i = 0; i < 6; i++) { int x2 = x + shift[i].first; int y2 = y + shift[i].second; if(is_safe(n,x2,y2) && !(a[x2][y2].visited)) { //cout << i << " " << x2 << " " << y2 << endl; a[x2][y2].visited = true; v.push(make_pair(x2,y2)); a[x2][y2].sh = i; a[x2][y2].px = x; a[x2][y2].py = y; a[x2][y2].d = a[x][y].d + 1; if(x2 == ie && y2 == je) { flag = true; break; } } } if(flag) { break; } } if(v.empty()) { cout << "Impossible" << endl; return 0; } //cout << "temp" << endl; vector o; x = ie; y = je; int x2; while(!(x == is && y == js)) { //cout << x << " " << y << endl; //cout << a[x][y].px << " " << a[x][y].py << endl; o.push_back(a[x][y].sh); x2 = a[x][y].px; y = a[x][y].py; x = x2; } //cout << "temp" << endl; cout << a[ie][je].d << endl; for(int i = o.size() - 1; i >= 0; i--) { cout << ord[o[i]] << " "; } cout << endl; return 0; } bool is_safe(int n, int x, int y) { return x >= 0 && x < n && y >= 0 && y < n; }