#include using namespace std ; #define mod 1000000007 #define ull unsigned long long int #define ll long long int #define pb push_back #define SPEED cin.sync_with_stdio(0);cin.tie(0); inline void make_adjacency_list( vector< vector< vector< pair > > > &graph , int n ){ for(int i=0;i temp ; // pushing UL=0 in the adjacency list of the node. if( i-2>=0 && j-1>=0 ){ temp.first = i-2 , temp.second = j-1 ; graph[i][j].pb(temp) ; } // pushing UR=1 in the adjacency list of the node. if( i-2>=0 && j+1<=n-1 ){ temp.first = i-2 , temp.second = j+1 ; graph[i][j].pb(temp) ; } // pushing R=2 in the adjacency list of the node. if( j+2<=n-1 ){ temp.first = i , temp.second = j+2 ; graph[i][j].pb(temp) ; } // pushing LR=3 in the adjacency list of the node. if( i+2<=n-1 && j+1<=n-1 ){ temp.first = i+2 , temp.second = j+1 ; graph[i][j].pb(temp) ; } // pushing LL=4 in the adjacency list of the node. if( i+2<=n-1 && j-1>=0 ){ temp.first = i+2 , temp.second = j-1 ; graph[i][j].pb(temp) ; } // pushing L=5 in the adjacency list of the node. if( j-2>=0 ){ temp.first = i , temp.second = j-2 ; graph[i][j].pb(temp) ; } } } } inline void print_vector(vector &arr){ for(int i=0;i > > > &graph , vector< vector > > &parent , vector< vector > &visited , vector< vector > &distance , int start_x , int start_y , int end_x , int end_y ){ // function starts here . pair root ; root.first = start_x , root.second = start_y ; queue< pair > q ; visited[root.first][root.second] = 1 ; q.push(root) ; while( q.size() > 0 ){ for(int i=0 ; i < graph[q.front().first][q.front().second].size() ; i++){ if( visited [ graph[q.front().first][q.front().second][i].first ] [ graph[q.front().first][q.front().second][i].second ] == 0 // checking unvisited . ){ visited [ graph[q.front().first][q.front().second][i].first ] [ graph[q.front().first][q.front().second][i].second ] = 1 ; // visiting . parent [ graph[q.front().first][q.front().second][i].first ] [ graph[q.front().first][q.front().second][i].second ] = q.front() ; // setting parent . distance [ graph[q.front().first][q.front().second][i].first ] [ graph[q.front().first][q.front().second][i].second ] = 1 + distance[q.front().first][q.front().second] ; // setting the distance . q.push( graph[q.front().first][q.front().second][i] ) ; } } q.pop() ; } } inline void track_path ( // parameters . pair root , pair dest , vector< vector > > &parent , vector > &path ) { // function starts here . pair curr = dest ; while( curr!=root ){ path.pb(curr) ; curr = parent[ curr.first ][ curr.second ] ; } path.pb(root) ; reverse(path.begin(),path.end()) ; } inline int give_rank ( pair root , pair dest ) { int val = 0 ; if( root.first-2==dest.first && root.second-1==dest.second ){ val = 0 ; } else if( root.first-2==dest.first && root.second+1==dest.second ){ val = 1 ; } else if( root.first==dest.first && root.second+2==dest.second ){ val = 2 ; } else if( root.first+2==dest.first && root.second+1==dest.second ){ val = 3 ; } else if( root.first+2==dest.first && root.second-1==dest.second ){ val = 4 ; } else if( root.first==dest.first && root.second-2==dest.second ){ val = 5 ; } return val ; } inline void print_path( vector > &path ){ for(int i=0;i>n ; int start_x , start_y , end_x , end_y ; cin>>start_x>>start_y>>end_x>>end_y ; // Containers to be used are defined here . vector< vector< vector< pair > > > graph( n , vector< vector > >(n) ) ; vector< vector > > parent ( n , vector< pair >(n) ) ; vector< vector > visited( n , vector (n,0) ) ; vector< vector > distance( n , vector (n,0) ) ; // Make adjaceny list function is called to make the adjacency list of the graph . make_adjacency_list(graph,n) ; // Process to compute the answer . bfs( graph , parent , visited , distance , start_x , start_y , end_x , end_y ) ; // Outputing the answer . if(visited[end_x][end_y]==0){ cout<<"Impossible\n"; } else{ cout< > path ; pair root ; root.first = start_x , root.second = start_y ; pair dest ; dest.first = end_x , dest.second = end_y ; track_path( root , dest , parent , path ) ; print_path( path ) ; } return 0 ; }