#include #define move pair< pair, vector *> #define mp(a, b) make_pair(a, b) #define vs vector #define cord pair using namespace std; class Sorter{ vector s {"UL", "UR", "R", "LR", "LL", "L"}; public: bool operator() (string i, string j){ ptrdiff_t pos1 = find(s.begin(), s.end(), i) - s.begin(); ptrdiff_t pos2 = find(s.begin(), s.end(), j) - s.begin(); return pos1 < pos2; } }; inline bool isSafe(int cx, int cy, int n){ return (cx < n) && (cx >= 0) && (cy < n) && (cy >= 0); } inline void push_into_queue(queue &q, vector< vector > &visited, vs *vec, int x, int y, int n, string m) { if(isSafe(x, y, n) && !visited[x][y]){ vs *s = new vs(vec->begin(), vec->end()); s->push_back(m); q.push(mp(mp(x, y), s)); visited[x][y] = true; } } vector* printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { vector< vector > visited(n, vector(n, false)); queue q; vs *s = new vs(); q.push(mp(mp(i_start, j_start), s)); visited[i_start][j_start] = true; while(!q.empty()) { move m = q.front(); q.pop(); cord c = m.first; int curr_x = c.first, curr_y = c.second; //cout << curr_x << " " << curr_y << endl; if(curr_x == i_end && curr_y == j_end){ return m.second; } push_into_queue(q, visited, m.second, curr_x, curr_y-2, n, "L"); push_into_queue(q, visited, m.second, curr_x, curr_y+2, n, "R"); push_into_queue(q, visited, m.second, curr_x-2, curr_y+1, n, "UR"); push_into_queue(q, visited, m.second, curr_x-2, curr_y-1, n, "UL"); push_into_queue(q, visited, m.second, curr_x+2, curr_y+1, n, "LR"); push_into_queue(q, visited, m.second, curr_x+2, curr_y-1, n, "LL"); delete m.second; } return NULL; } int main() { int n; cin >> n; int i_start; int j_start; int i_end; int j_end; cin >> i_start >> j_start >> i_end >> j_end; vs *s = printShortestPath(n, i_start, j_start, i_end, j_end); //cout << s << endl; if(!s) cout << "Impossible" << endl; else { Sorter cmp; sort(s->begin(), s->end(), cmp); cout << s->size() << endl; for(int i = 0; i < s->size(); ++i) cout << s->at(i) << " "; cout << endl; } return 0; }