#include #include #include #include #include #include #include using namespace std; #define UL 1 #define UR 2 #define R 3 #define LR 4 #define LL 5 #define L 6 #define mp(i,j) make_pair(i,j) #define pb(i) push_back(i) #define fi first #define se second typedef pair pii; pii getNextPos(pii currPos, int moveNum){ int x = currPos.fi; int y = currPos.se; pii res; switch(moveNum){ case UL: res = make_pair(x-2,y-1); break; case UR: res = make_pair(x-2,y+1); break; case R: res = make_pair(x,y+2); break; case LR: res = make_pair(x+2,y+1); break; case LL: res = make_pair(x+2,y-1); break; case L: res = make_pair(x,y-2); } return res; } string getMoveLiteral(int moveNum){ string res; switch(moveNum){ case UL: res = "UL"; break; case UR: res = "UR"; break; case R: res = "R"; break; case LR: res = "LR"; break; case LL: res = "LL"; break; case L: res = "L"; } return res; } int n; pii start,des; bool vis[205][205]; pii par[205][205]; int mov[205][205]; bool isValidPos(pii point){ if(point.fi >= 0 && point.se >= 0 && point.fi < n && point.se < n){ return 1; } return 0; } inline void read(){ cin>>n; int x1,y1,x2,y2; cin>>x1>>y1>>x2>>y2; start = make_pair(x1,y1); des = make_pair(x2,y2); for(int i=0;i<205;i++){ for(int j=0;j<205;j++){ vis[i][j] = 0; par[i][j] = mp(-1,-1); mov[i][j] = -1; } } } int main() { read(); queue q; q.push(start); bool desFound = 0; while(!q.empty()){ pii curr = q.front(); q.pop(); if(curr == des){ desFound = 1; break; } //UL Case pii ulCand = getNextPos(curr,UL); if(isValidPos(ulCand) && !vis[ulCand.fi][ulCand.se]){ q.push(ulCand); par[ulCand.fi][ulCand.se] = curr; mov[ulCand.fi][ulCand.se] = UL; vis[ulCand.fi][ulCand.se] = 1; } //UR Case pii urCand = getNextPos(curr,UR); if(isValidPos(urCand) && !vis[urCand.fi][urCand.se]){ q.push(urCand); par[urCand.fi][urCand.se] = curr; mov[urCand.fi][urCand.se] = UR; vis[urCand.fi][urCand.se] = 1; } //R Case pii rCand = getNextPos(curr,R); if(isValidPos(rCand) && !vis[rCand.fi][rCand.se]){ q.push(rCand); par[rCand.fi][rCand.se] = curr; mov[rCand.fi][rCand.se] = R; vis[rCand.fi][rCand.se] = 1; } //LR CASE pii lrCand = getNextPos(curr,LR); if(isValidPos(lrCand) && !vis[lrCand.fi][lrCand.se]){ q.push(lrCand); par[lrCand.fi][lrCand.se] = curr; mov[lrCand.fi][lrCand.se] = LR; vis[lrCand.fi][lrCand.se] = 1; } //LL CASE pii llCand = getNextPos(curr,LL); if(isValidPos(llCand) && !vis[llCand.fi][llCand.se]){ q.push(llCand); par[llCand.fi][llCand.se] = curr; mov[llCand.fi][llCand.se] = LL; vis[llCand.fi][llCand.se] = 1; } //L CASE pii lCand = getNextPos(curr,L); if(isValidPos(lCand) && !vis[lCand.fi][lCand.se]){ q.push(lCand); par[lCand.fi][lCand.se] = curr; mov[lCand.fi][lCand.se] = L; vis[lCand.fi][lCand.se] = 1; } } if(!desFound){ cout<<"Impossible"; }else{ stack moves; pii curr = des; int totalMoves = 0; while(curr != start){ moves.push(mov[curr.fi][curr.se]); ++totalMoves; //cout<