#include using namespace std; const int START = 0; const int UL = 1; const int UR = 2; const int R = 3; const int LR = 4; const int LL = 5; const int L = 6; class Node { public: int i; int j; int step; int dist; int cost; int counter; Node* parent; void print(); }; void Node::print() { cout << i << " " << j << " " << dist << " " << counter << endl; } class Compare { public: bool operator() (Node* i, Node* j) { if (i->cost == j->cost) { return i->counter > j->counter; } return i->cost > j->cost; } }; int man_dist(int i_start, int j_start, int i_end, int j_end) { int dist = abs(i_start-i_end) + abs(j_start-j_end); return dist; } string convert_val(int i) { if (i == UL) { return "UL"; } else if (i == UR) { return "UR"; } else if (i == R) { return "R"; } else if (i == LR) { return "LR"; } else if (i == LL) { return "LL"; } else if (i == L) { return "L"; } return ""; } void print_chain(Node* current, bool is_end) { if (current->parent != nullptr) { print_chain(current->parent, false); cout << convert_val(current->counter); if (is_end) { cout << endl; } else { cout << " "; } } } void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { // Print the distance along with the sequence of moves. int dist = man_dist(i_start, j_start, i_end, j_end); Node* first_node = new Node; first_node->i = i_start; first_node->j = j_start; first_node->step = 0; first_node->dist = dist; first_node->cost = dist; first_node->parent = nullptr; priority_queue, Compare > q; q.push(first_node); while (!q.empty()) { Node* current = q.top(); q.pop(); int dist = current->dist; if (dist == 1) { cout << "Impossible" << endl; break; } else if (dist == 0) { cout << current->cost << endl; print_chain(current, true); break; } for (int i=UL; i<=L; ++i) { int i_step; int j_step; if (i==UL) { i_step = -2; j_step = -1; } else if (i==UR) { i_step = -2; j_step = 1; } else if (i==R) { i_step = 0; j_step = 2; } else if (i==LR) { i_step = 2; j_step = 1; } else if (i==LL) { i_step = 2; j_step = -1; } else if (i==L) { i_step = 0; j_step = -2; } int new_i = current->i+i_step; int new_j = current->j+j_step; if (new_i >= 0 && new_i < n && new_j >= 0 && new_j < n) { Node* new_node = new Node; new_node->i = new_i; new_node->j = new_j; new_node->step = current->step+1; new_node->dist = man_dist(new_i, new_j, i_end, j_end); new_node->cost = new_node->step+new_node->dist; new_node->counter = i; new_node->parent = current; q.push(new_node); } } } } 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; printShortestPath(n, i_start, j_start, i_end, j_end); return 0; }