// #include #include #include #include #include #include using namespace std; stack path; stack gpath; stack tmpath; set > s; int printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { // Print the distance along with the sequence of moves. // cout << i_start << " "<= n || j_start >= n){ return -1; } if (i_start == i_end && j_start == j_end){ tmpath = path; // cout << tmpath.top(); return 0; } if (abs(i_start - i_end) == 0 || (abs(i_start - i_end)) == 1){ if (abs(j_start - j_end) == 0 || (abs(j_start - j_end)) == 1){ return -1; } } int y = -1; if (s.find(make_pair(i_start-2, j_start-1)) == s.end()){ path.push("UL"); s.insert(make_pair(i_start-2, j_start-1)); int x = printShortestPath(n, i_start-2, j_start-1, i_end, j_end); if (x != -1){ y = 1 + x; if (gpath.size() > tmpath.size() || gpath.size() == 0){ gpath = tmpath; } } path.pop(); s.erase(make_pair(i_start-2, j_start-1)); } if (s.find(make_pair(i_start-2, j_start+1)) == s.end()){ path.push("UR"); s.insert(make_pair(i_start-2, j_start+1)); int x = printShortestPath(n, i_start-2, j_start+1, i_end, j_end); if (x != -1){ if (y == -1){ y = 1 + x; if (gpath.size() > tmpath.size() || gpath.size() == 0){ gpath = tmpath; } } else{ // y = min(y, 1+x); if (1 + x < y){ if (gpath.size() > tmpath.size() || gpath.size() == 0){ gpath = tmpath; } y = 1 + x; } } } path.pop(); s.erase(make_pair(i_start-2, j_start+1)); } if (s.find(make_pair(i_start, j_start+2)) == s.end()){ path.push("R"); s.insert(make_pair(i_start, j_start+2)); int x = printShortestPath(n, i_start, j_start+2, i_end, j_end); if (x != -1){ if (y == -1){ y = 1+x; if (gpath.size() > tmpath.size() || gpath.size() == 0){ gpath = tmpath; } } else{ if (1 + x < y){ if (gpath.size() > tmpath.size() || gpath.size() == 0){ gpath = tmpath; } y = 1 + x; } } } path.pop(); s.erase(make_pair(i_start, j_start+2)); } if (s.find(make_pair(i_start+2, j_start+1)) == s.end()){ path.push("LR"); s.insert(make_pair(i_start+2, j_start+1)); int x = printShortestPath(n, i_start+2, j_start+1, i_end, j_end); if (x != -1){ if (y == -1){ y = 1+x; if (gpath.size() > tmpath.size() || gpath.size() == 0){ gpath = tmpath; } } else{ if (1 + x < y){ if (gpath.size() > tmpath.size() || gpath.size() == 0){ gpath = tmpath; } y = 1 + x; } } } path.pop(); s.erase(make_pair(i_start+2, j_start+1)); } if (s.find(make_pair(i_start+2, j_start-1)) == s.end()){ path.push("LL"); s.insert(make_pair(i_start+2, j_start-1)); int x = printShortestPath(n, i_start+2, j_start-1, i_end, j_end); if (x != -1){ if (y == -1){ y = 1+x; if (gpath.size() > tmpath.size() || gpath.size() == 0){ gpath = tmpath; } } else{ if (1 + x < y){ if (gpath.size() > tmpath.size() || gpath.size() == 0){ gpath = tmpath; } y = 1 + x; } } } path.pop(); s.erase(make_pair(i_start+2, j_start-1)); } if (s.find(make_pair(i_start, j_start-2)) == s.end()){ path.push("L"); s.insert(make_pair(i_start, j_start-2)); int x = printShortestPath(n, i_start, j_start-2, i_end, j_end); if (x != -1){ if (y == -1){ y = 1+x; if (gpath.size() > tmpath.size() || gpath.size() == 0){ gpath = tmpath; } } else{ if (1 + x < y){ if (gpath.size() > tmpath.size() || gpath.size() == 0){ gpath = tmpath; } y = 1 + x; } } } path.pop(); s.erase(make_pair(i_start, j_start-2)); } if (y != -1){ return y; } return -1; } 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; int x = printShortestPath(n, i_start, j_start, i_end, j_end); if (x == -1){ cout << "Impossible"; } else{ cout << x< p; while(!gpath.empty()){ p.push(gpath.top()); gpath.pop(); } while(!p.empty()){ cout << p.top() << " "; p.pop(); } } return 0; }