#include using namespace std; /*int moves(int n, int i, int j, int k, int l , int **a,int **b) { b[i][j] = 1; int mm[] = {-3,-3,-3,-3,-3,-3}; if (i==k && j==l) {a[i][j] = 0; b[i][j] = 0; return 0; } if (i - 2 =0 && j-1 >=0 && b[i-2][j-1]!=1) { if (a[i-2][j-1] == -2) a[i-2][j-1] = moves(n,i-2,j-1,k,l,a,b); mm[0] = a[i-2][j-1]; } if (i - 2 =0 && j+1 >=0 && b[i-2][j+1]!=1) { if (a[i-2][j+1] == -2) a[i-2][j+1] = moves(n,i-2,j+1,k,l,a,b); mm[1] = a[i-2][j+1]; } if (i =0 && j+2 >=0 && b[i][j+2]!=1) { if (a[i][j+2] == -2) a[i][j+2] = moves(n,i,j+2,k,l,a,b); mm[2] = a[i][j+2]; } if (i+2 =0 && j+1 >=0 && b[i+2][j+1]!=1) { if (a[i+2][j+1] == -2) a[i+2][j+1] = moves(n,i+2,j+1,k,l,a,b); mm[3] = a[i+2][j+1]; } if (i+2 =0 && j-1 >=0 && b[i+2][j-1]!=1) { if (a[i+2][j-1] == -2) a[i+2][j-1] = moves(n,i+2,j-1,k,l,a,b); mm[4] = a[i+2][j-1]; } if (i =0 && j-2 >=0 && b[i][j-2]!=1) { if (a[i][j-2] == -2) a[i][j-2] = moves(n,i,j-2,k,l,a,b); mm[5] = a[i][j-2]; } int minimum = 30000; for (int i=0;i<6;i++) { if (mm[i] !=-3 && mm[i] != -1) { if (mm[i] < minimum) minimum = mm[i]; } } a[i][j] = 1+ minimum; if (a[i][j] = 30001) a[i][j] = -1; b[i][j] = 0; return a[i][j]; } */ 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. int **dptable; int **visited; dptable = (int**)malloc(n*sizeof(int*)); visited = (int**)malloc(n*sizeof(int*)); for (int i=0;i > q; vector > > parent(n,vector >(n)); q.push(make_pair(i_start,j_start)); pair t; dptable[i_start][j_start] = 0; visited[i_start][j_start] = 1; parent[i_start][j_start] = make_pair(-1,-1); while(!q.empty()) { t = q.front(); q.pop(); int i = t.first; int j= t.second; if (i == i_end && j == j_end) { break; } if (i - 2 =0 && j-1 >=0 && visited[i-2][j-1]!=1) { q.push(make_pair(i-2,j-1)); visited[i-2][j-1] = 1; dptable[i-2][j-1] = dptable[i][j] +1; parent[i-2][j-1] = make_pair(i,j); } if (i - 2 =0 && j+1 >=0 && visited[i-2][j+1]!=1) { q.push(make_pair(i-2,j+1)); visited[i-2][j+1] = 1; dptable[i-2][j+1] = dptable[i][j] +1; parent[i-2][j+1] = make_pair(i,j); } if (i =0 && j+2 >=0 && visited[i][j+2]!=1) { q.push(make_pair(i,j+2)); visited[i][j+2] = 1; dptable[i][j+2] = dptable[i][j] +1; parent[i][j+2] = make_pair(i,j); } if (i+2 =0 && j+1 >=0 && visited[i+2][j+1]!=1) { q.push(make_pair(i+2,j+1)); visited[i+2][j+1] = 1; dptable[i+2][j+1] = dptable[i][j] +1; parent[i+2][j+1] = make_pair(i,j); } if (i+2 =0 && j-1 >=0 && visited[i+2][j-1]!=1) { q.push(make_pair(i+2,j-1)); visited[i+2][j-1] = 1; dptable[i+2][j-1] = dptable[i][j] +1; parent[i+2][j-1] = make_pair(i,j); } if (i =0 && j-2 >=0 && visited[i][j-2]!=1) { q.push(make_pair(i,j-2)); visited[i][j-2] = 1; dptable[i][j-2] = dptable[i][j] +1; parent[i][j-2] = make_pair(i,j); } }; if (dptable[i_end][j_end]==-2) cout<<"Impossible"; else cout< x = make_pair(i_end,j_end); pair p = parent[i_end][j_end]; vector ans; while (p.first!= -1 && p.second!= -1) { int a = p.first - x.first; int b= p.second - x.second; if (a == -2 && b== -1) { ans.push_back(1); } if (a == -2 && b== 1) { ans.push_back(2); } if (a == 0 && b== 2) { ans.push_back(3); } if (a == 2 && b== 1) { ans.push_back(4); } if (a == 2 && b== -1) { ans.push_back(5); } if (a == 0 && b== -2) { ans.push_back(6); } x = p; p = parent[x.first][x.second]; }; reverse(ans.begin(),ans.end()); for (int i=0;i> 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; }