#include #define vi vector #define pb push_back #define mp make_pair #define pp pair using namespace std; int x[6] = {-2, -2, 0, 2, 2, 0}; int y[6] = {-1, 1, 2, 1, -1, -2}; string name[6] = {"UL", "UR", "R", "LR", "LL", "L"}; int conv(int i, int j, int n){ return i*n + j; } bool isSafe(int i, int j, int f, int n, vector &seen){ if(i>=0 and j>=0 and i > q; vi len(n*n), move(n*n); vector seen(n*n); q.push(mp(i_start, j_start)); tmp = conv(i_start, j_start, n); move[tmp] = -1; len[tmp] = 0; seen[tmp] = 1; pp dest = mp(i_end, j_end); int destInd = conv(i_end, j_end, n); bool foundDest = false; while(!q.empty()){ pp curr = q.front(); q.pop(); if(curr == dest){ foundDest = 1; break; } tmp1 = curr.first; tmp2 = curr.second; for(int i=0;i<6;i++){ int newX = tmp1 + x[i]; int newY = tmp2 + y[i]; int ind = conv(newX, newY, n); if(isSafe(newX, newY, ind, n, seen)){ q.push(mp(newX, newY)); seen[ind] = 1; len[ind] = len[conv(tmp1, tmp2, n)]+1; move[ind] = i; } } } if(!seen[destInd]){ cout<<"Impossible"< out; int cur = conv(i_end, j_end,n); tmp = i_end; tmp1= j_end; while(move[cur]>=0){ // cout<<"asd"<<" "<=0;i--) 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; }