#include using namespace std; struct cmp{ bool operator() (pair, string> &x, pair, string> &y){ return x.first.back() > y.first.back(); } }; 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. priority_queue, string>, vector, string> >, cmp> Q; pair, string> sp = make_pair(vector{i_start, j_start, 0}, ""); Q.push(sp); vector > visited(n, vector(n, false)); vector> rec_moves(n ,vector(n, "")); vector> rec_mins(n, vector(n, INT_MAX)); int min_temp = INT_MAX; vector> d{{-2, -1}, {-2, 1}, {0, 2}, {2, 1}, {2, -1}, {0, -2}}; vector moves{"UL", "UR", "R", "LR", "LL", "L"}; map prior; for(int i = 0; i < 6; i++) prior[moves[i]] = 6-i; while(!Q.empty()){ pair, string> p = Q.top(); Q.pop(); int step = p.first.back(), px = p.first[0], py = p.first[1]; string last_move = p.second; if(rec_mins[px][py] > step){ rec_mins[px][py] = step; rec_moves[px][py] = last_move; } else if(rec_mins[px][py] == step){ if(prior[last_move] > prior[rec_moves[px][py]]) rec_moves[px][py] = last_move; } if(px == i_end && py == j_end){ if(step < min_temp) min_temp = step; continue; } visited[px][py] = true; for(int i = 0; i < 6; i++){ int dx = px + d[i][0], dy = py + d[i][1]; if(dx >= 0 && dx < n && dy >= 0 && dy < n && !visited[dx][dy]) Q.push(make_pair(vector{dx, dy, step+1}, moves[i])); } } if(rec_mins[i_end][j_end] == INT_MAX){ cout<<"Impossible"< bm = d[6-prior[s]]; i -= bm[0]; j -= bm[1]; } cout<> 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; }