#include using namespace std; const int OO = 1E9; int dirI[] = {-2,-2,0,2, 2, 0}; int dirJ[] = {-1, 1,2,1,-1,-2}; string arr[] = {"UL","UR","R","LR","LL","L"}; void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { int N = n*n; vector vis(N,false); vector parent(N,-1); vector print(N,-1); vis[i_start * n + j_start] = true; queue > pq; pq.push(make_pair(0,i_start * n + j_start)); while(!pq.empty()) { pair curr = pq.front(); pq.pop(); int currJ = curr.second % n; int currI = (curr.second-currJ)/n; for(int i = 0;i<6;i++) { int nextI = currI + dirI[i], nextJ = currJ + dirJ[i]; int nextNode = nextI*n+nextJ; if( nextI >= 0 && nextI < n && nextJ >= 0 && nextJ < n && !vis[nextNode]) { vis[nextNode] = true; parent[nextNode] = curr.second; print[nextNode] = i; pq.push(make_pair(curr.first+1,nextNode)); } } } int last = i_end * n + j_end; if(parent[last] == -1) cout<<"Impossible"; else { vector temp; while(parent[last] != -1) { temp.push_back(print[last]); last = parent[last]; } 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; }