#include using namespace std; struct Point{ int i; int j; string dir; Point(int i, int j, const char* dir):i(i), j(j), dir(dir){} Point ():i(0), j(0), dir(""){} }; typedef std::shared_ptr PointPtr; vector getChildren(Point& p, int n){ vector out; //add UL child if exists if (p.j - 1 >= 0 && p.i-2 >=0){ out.push_back(Point(p.i-2, p.j-1,"UL")); } if (p.j + 1 < n && p.i-2 >=0){ out.push_back(Point(p.i-2, p.j+1, "UR")); } if (p.j + 2 < n){ out.push_back(Point(p.i, p.j+2, "R")); } if (p.j + 1 = 0 && p.i+2 < n){ out.push_back(Point(p.i+2, p.j-1, "LL")); } if (p.j - 2 >=0){ out.push_back(Point(p.i, p.j-2, "L")); } return out; } void printPath(vector>& parent, int i_end, int j_end){ Point& curr = parent[i_end][j_end]; string path; int length = 0; while (!(curr.i == -1 && curr.j == -1)){ path = curr.dir + " " + path; length++; curr = parent[curr.i][curr.j]; } cout << length << endl << path << endl; } 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. vector> visited(n, vector(n, false)); vector> parent(n, vector(n)); Point start(i_start, j_start, ""); visited[i_start][j_start] = true; parent[i_start][j_start] = Point(-1,-1,""); std::deque q; q.push_back(start); while (!q.empty()){ Point& curr = q.front(); q.pop_front(); vector children = getChildren(curr, n); for (int i = 0; i < children.size(); i++){ Point& child = children[i]; if (!visited[child.i][child.j]){ visited[child.i][child.j] = true; parent[child.i][child.j] = Point(curr.i, curr.j, child.dir.c_str()); q.push_back(child); if (child.i == i_end && child.j == j_end){ printPath(parent, i_end, j_end); return; } } } } //no path found printf("Impossible\n"); } 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; }