#include #include using namespace std; #define debug(x) cout<<#x<<" :: "< pii; const int N = 1e5 + 5; /***************************************************************************/ string way_str[] = {"UL", "UR", "R", "LR", "LL", "L"}; int dx[6] = {-2, -2, 0, 2, 2, 0}; int dy[6] = {-1, 1, 2, 1, -1, -2}; 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. queue Q; Q.emplace(i_start, j_start); pii par[n][n]; int way[n][n]; memset(par, -1, sizeof par); while(!Q.empty()) { pii v = Q.front(); Q.pop(); for(int i=0; i<6; i++) { int x = v.first + dx[i]; int y = v.second + dy[i]; if(x >= 0 && x < n && y >= 0 && y < n && par[x][y].first == -1) { par[x][y] = v; way[x][y] = i; Q.emplace(x, y); } } } if(par[i_end][j_end].first == -1) { cout<<"Impossible\n"; return; } stack stk; pii v(i_end, j_end); while(v != pii(i_start, j_start)) { stk.push(way[v.first][v.second]); v = par[v.first][v.second]; } 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; }