#include using namespace std; int distance(pair a,pair b){ return abs(a.first-b.first)+abs(a.second-b.second); } stack steps; bool solved=false; pair Sum(pair a,pair b){return make_pair(a.first+b.first,b.second+a.second);} void Fill(pair a,pair goal,int size,int dist){ if(a.first>=size||a.second>=size||a.first<0||a.second<0)return; if(dist==0){ solved=true;return; } int minn=dist; pair step=make_pair(0,0); for(int i=-2;i<2;i+=2){ pair currentStep1=make_pair(i,1+(abs(i)!=2)); if(minn>=distance(Sum(a,currentStep1),goal)){ minn=distance(Sum(a,currentStep1),goal); step=currentStep1; } pair currentStep2=make_pair(i,-(1+(abs(i)!=2))); if(minn>=distance(Sum(a,currentStep2),goal)){ minn=distance(Sum(a,currentStep2),goal); step=currentStep2; } } if(step==make_pair(0,0)){return;} string solution="PP"; if(step.first<0)solution[1]='L'; if(step.first>0)solution[1]='R'; if(step.second==0)solution.erase(solution.begin()); if(step.second>0)solution[0]='L'; if(step.second>0)solution[0]='R'; steps.push(solution); Fill(Sum(a,step),goal,size,distance(Sum(a,step),goal)); } 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. pair coord1,coord2; coord1=make_pair(i_start,j_start); coord2=make_pair(i_end,j_end); Fill(coord2,coord1,n,distance(coord1,coord2)); if(!solved){ cout <<"Impossible"<> 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; }