#include #include #include #include #define INF 2<<29 #define N 201 using namespace std; struct Elem { int x, y, cost; bool operator<(const Elem &rhs) const { if (cost > rhs.cost) return true; else if (cost == rhs.cost) { if (x > rhs.x) return true; else if (x == rhs.x) { if (y < rhs.y) return true; } } return false; } }; string get_direction(int prev_x, int prev_y, int pos_x, int pos_y) { if (prev_x - 2 == pos_x && prev_y - 1 == pos_y) return "UL"; else if (prev_x - 2 == pos_x && prev_y + 1 == pos_y) return "UR"; else if (prev_x == pos_x && prev_y + 2 == pos_y) return "R"; else if (prev_x + 2 == pos_x && prev_y + 1 == pos_y) return "LR"; else if (prev_x + 2 == pos_x && prev_y - 1 == pos_y) return "LL"; else if (prev_x == pos_x && prev_y - 2 == pos_y) return "L"; else return "Very unlikely to reach this point. Good luck!\n"; } void reconstruct(vector > trace, int pos_x, int pos_y) { if (trace[pos_x][pos_y].x != -1 && trace[pos_x][pos_y].y != -1) { Elem prev = trace[pos_x][pos_y]; reconstruct(trace, prev.x, prev.y); cout << get_direction(prev.x, prev.y, pos_x, pos_y) << " "; } } 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 dx[6] = {-2, -2, 0, 2, 2, 0}; int dy[6] = {-1, 1, 2, 1, -1, -2}; vector > cost(n, vector(n)); vector > trace(n, vector(n)); for (int i=0; i q; q.push(Elem{i_start, j_start, 0}); cost[i_start][j_start] = 0; while (!q.empty()) { Elem node = q.top(); q.pop(); for (int d=0; d<6; ++d) { Elem new_node{node.x + dx[d], node.y + dy[d], node.cost + 1}; if (new_node.x >= 0 && new_node.x < n && new_node.y >= 0 && new_node.y < n && new_node.cost < cost[new_node.x][new_node.y]) { cost[new_node.x][new_node.y] = new_node.cost; trace[new_node.x][new_node.y] = {node.x, node.y}; q.push(new_node); } } } if (cost[i_end][j_end] != INF) { cout << cost[i_end][j_end] << "\n"; reconstruct(trace, i_end, j_end); } else { cout << "Impossible"; } } 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; }