#include #include using namespace std; struct direction{ bool left,up,right,down; }; struct Node{ pair coor; Node * parent; string dir; }; int cnt=0; Node * newNode(pair p) { Node * n=new Node; n->coor=p; n->parent=NULL; return n; } direction getdir(Node *s,int dx,int dy) { int sx=(s->coor).first,sy=(s->coor).second; direction d; d.left=d.up=0,d.right=0,d.down=0; int diff1,diff2; diff2=sx-dx; diff1=sy-dy; if(diff1>0) d.left=1; else if(diff1<0) d.right=1; if(diff2>0) d.up=1; else if(diff2<0) d.down=1; return d; } bool validate_index(int x,int n) { if(x>=0 && x >& v,queue& q) { int px,py,cx,cy; px=(p->coor).first; py=(p->coor).second; { if(validate_index(px-2,n) && validate_index(py-1,n)) { cx=px-2; cy=py-1; pairtemp; temp.first=cx; temp.second=cy; if(v.find(temp)==v.end()) { Node * c=newNode(temp); c->parent=p; q.push(c); c->dir="UL"; v.insert(temp); } } if(validate_index(px-2,n) && validate_index(py+1,n)) { cx=px-2; cy=py+1; pairtemp; temp.first=cx; temp.second=cy; if(v.find(temp)==v.end()) { Node * c=newNode(temp); c->parent=p; q.push(c); c->dir="UR"; v.insert(temp); } } if(validate_index(px,n) && validate_index(py+2,n)) { cx=px; cy=py+2; pairtemp; temp.first=cx; temp.second=cy; if(v.find(temp)==v.end()) { Node * c=newNode(temp); c->parent=p; q.push(c); c->dir="R"; v.insert(temp); } } if(validate_index(px+2,n) && validate_index(py+1,n)) { cx=px+2; cy=py+1; pairtemp; temp.first=cx; temp.second=cy; if(v.find(temp)==v.end()) { Node * c=newNode(temp); c->parent=p; q.push(c); c->dir="LR"; v.insert(temp); } } if(validate_index(px+2,n) && validate_index(py-1,n)) { cx=px+2; cy=py-1; pairtemp; temp.first=cx; temp.second=cy; if(v.find(temp)==v.end()) { Node * c=newNode(temp); c->parent=p; q.push(c); c->dir="LL"; v.insert(temp); } } if(validate_index(px,n) && validate_index(py-2,n)) { cx=px; cy=py-2; pairtemp; temp.first=cx; temp.second=cy; if(v.find(temp)==v.end()) { Node * c=newNode(temp); c->parent=p; q.push(c); c->dir="L"; v.insert(temp); } } } } bool not_possible(Node * s,int dx,int dy) { int sx=(s->coor).first,sy=(s->coor).second; int diff1=abs(sx-dx),diff2=abs(sy-dy); if(diff1==1 && diff2==1) return 1; else if(diff1==1 && diff2==0) return 1; else if(diff1==0 && diff2==1) return 1; else return 0; } void printShortestPath(int n, int i_start, int i_end, int j_start, int j_end) { // Print the distance along with the sequence of moves. set< pair > visited; queue q; pair s,d; s.first=i_start; s.second=i_end; d.first=j_start; d.second=j_end; Node * temp=newNode(s); q.push(temp); visited.insert(make_pair(i_start,i_end)); direction dir; while(!q.empty()) { temp=q.front(); q.pop(); if((temp->coor)==d) break; if(not_possible(temp,j_start,j_end)) { cout<<"Impossible"; return; } dir=getdir(temp,j_start,j_end); insert_child(temp,dir,n,visited,q); } vector moves; while(temp->parent!=NULL) { cnt++; moves.push_back(temp->dir); temp=temp->parent; } cout<=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; }