#include #define f first #define s second #define mp make_pair #define pb push_back #define lp(i,a,n) for(int i=a;i<=n;++i) #define lpd(i,a,n) for(int i=a;i>=n;--i) #define mem(a,b) memset(a,b,sizeof a) #define all(v) v.begin(),v.end() #define println(a) cout <<(a) < pii; typedef pair pll; typedef vector vi; typedef vector vvi; typedef vector vll; typedef set si; typedef map mii; const int N = 100002; string arr[] = {"UL","UR","R","LR","LL","L"}; int dirI[] = {-2,-2,0,2, 2, 0}, dirJ[] = {-1, 1,2,1,-1,-2}; void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { int N = n*n; vector vis(N,false); vi parent(N,-1); vi print(N,-1); vis[i_start * n + j_start] = true; queue pq; pq.push(mp(0,i_start * n + j_start)); while(sz(pq)) { pii curr = pq.front(); pq.pop(); int currJ = curr.second % n; int currI = (curr.second-currJ)/n; lp(i,0,5) { int nextI = currI + dirI[i], nextJ = currJ + dirJ[i]; int nextNode = nextI*n+nextJ; if( nextI >= 0 and nextI < n and nextJ >= 0 and nextJ < n and !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 { vi temp; while(parent[last] != -1) { temp.push_back(print[last]); last = parent[last]; } cout<> i_start >> j_start >> i_end >> j_end; printShortestPath(n, i_start, j_start, i_end, j_end); } /* freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); */