#include #include #include #include #include #include #include #include #include #include #define REP(x,l,u) for(int x = (l);x<=(u);x++) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair pii; const ll llmax=9223372036854775807; const ll llmin=-9223372036854775808; const int intmin=-2147483648; const int intmax=2147483647; const int mod=1e9+7; ll gcd(ll a,ll b){if(a==0 || b==0) return a+b;else return gcd(b,a%b);} template inline A fexp(A x,B p){A ans=1;for(;p;p>>=1,x=1LL*x*x%mod)if(p&1)ans=1LL*ans*x%mod;return ans;} template inline void read(T &x){ x=0;T f=1;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do x=x*10+ch-'0',ch=getchar();while(ch<='9'&&ch>='0');x*=f; } class ST{ struct Node{ int l,r; ll sm,bjc,bjj; ll min; ll max; ll oor; ll andd; }; vector A; vector T; public: ST(vector& AA) { A.emplace_back(0);//to make it 1 indexed for(int i=0;i>1; build(i<<1,l,M);build(i<<1|1,M+1,r); pushup(i); } ll querySum(int i,int l,int r){ if(l<=T[i].l&&T[i].r<=r)return T[i].sm;// int M=T[i].l+T[i].r>>1;ll ans=0; pushdown(i); if(l<=M)ans+=querySum(i<<1,l,r);if(r>M)ans+=querySum(i<<1|1,l,r); return ans; } ll queryOr(int i,int l,int r){ if(l<=T[i].l&&T[i].r<=r)return T[i].oor;//((T[i].oor-T[i].andd)-(T[i].max-T[i].min)); int M=T[i].l+T[i].r>>1;ll ans=0; pushdown(i); if(l<=M)ans=queryOr(i<<1,l,r);if(r>M)ans|=queryOr(i<<1|1,l,r); return ans; } ll queryAnd(int i,int l,int r){ if(l<=T[i].l&&T[i].r<=r)return T[i].andd;//((T[i].oor-T[i].andd)-(T[i].max-T[i].min)); int M=T[i].l+T[i].r>>1;ll ans=0; pushdown(i); bool set=false; if(l<=M)ans=queryAnd(i<<1,l,r),set=true; if(r>M)ans=set?(ans&queryAnd(i<<1|1,l,r)):queryAnd(i<<1|1,l,r); return ans; } ll queryMax(int i,int l,int r){ if(l<=T[i].l&&T[i].r<=r)return T[i].max;//((T[i].oor-T[i].andd)-(T[i].max-T[i].min)); int M=T[i].l+T[i].r>>1;ll ans=llmin; pushdown(i); if(l<=M)ans=max(ans,queryMax(i<<1,l,r)); if(r>M)ans=max(ans,queryMax(i<<1|1,l,r)); return ans; } ll queryMin(int i,int l,int r){ if(l<=T[i].l&&T[i].r<=r)return T[i].min;//((T[i].oor-T[i].andd)-(T[i].max-T[i].min)); int M=T[i].l+T[i].r>>1;ll ans=llmax; pushdown(i); if(l<=M)ans=min(ans,queryMin(i<<1,l,r)); if(r>M)ans=min(ans,queryMin(i<<1|1,l,r)); return ans; } void add(int i,int l,int r,ll x){ if(l<=T[i].l&&T[i].r<=r){ add(i,x); return; } int M=T[i].l+T[i].r>>1; pushdown(i); if(l<=M)add(i<<1,l,r,x);if(r>M)add(i<<1|1,l,r,x); pushup(i); } void mul(int i,int l,int r,ll x){ if(l<=T[i].l&&T[i].r<=r){ mul(i,x); return; } int M=T[i].l+T[i].r>>1; pushdown(i); if(l<=M)mul(i<<1,l,r,x);if(r>M)mul(i<<1|1,l,r,x); pushup(i); } }; struct trip{ trip(int _len,int _l,int _r):len(_len),l(_l),r(_r){}; int len; int l; int r; }; struct MyClassLessThan { bool operator() (const trip & left, const trip & right) { return left.len < right.len; } }; bool same2more=false; bool isPossible(string& st1,string& st2){ vector dif; REP(i,0,st1.size()-1){ if(st1[i]!=st2[i]){ dif.emplace_back(i); } } if(dif.size()==0 && same2more) return true; else if(dif.size()==2 && st1[dif[0]]==st2[dif[1]] && st1[dif[1]]==st2[dif[0]]) return true; else return false; } int matrix[4][1001]; int dp[1001]; int count1(int xtop,int ytop,int sizex,int sizey){ int cnt=0; REP(x,0,sizex-1){ REP(y,0,sizey-1){ if(matrix[ytop-y][xtop-x]==1) cnt++; } } return cnt; } int check(int xtop,int ytop,int sizex,int sizey){ return count1(xtop,ytop,sizex,sizey)>0?1:0; } bool board[201][201]; int n; struct node{ node(node* pr,pair loc){ parent=pr; location=loc; } node* parent=NULL; vector> children; vector moveNames; void addChildren(){ if(location.first-1>=0 && location.second-2>=0 && !board[location.first-1][location.second-2]) moveNames.emplace_back("UL"), board[location.first-1][location.second-2]=true, children.emplace_back(make_pair(location.first-1,location.second-2)); if(location.first+1<=n-1 && location.second-2>=0 && !board[location.first+1][location.second-2]) moveNames.emplace_back("UR"), board[location.first+1][location.second-2]=true, children.emplace_back(make_pair(location.first+1,location.second-2)); if(location.first+2<=n-1 && location.second-0>=0 && !board[location.first+2][location.second-0]) moveNames.emplace_back("R"), board[location.first+2][location.second-0]=true, children.emplace_back(make_pair(location.first+2,location.second-0)); if(location.first+1<=n-1 && location.second+2<=n-1 && !board[location.first+1][location.second+2]) moveNames.emplace_back("LR"), board[location.first+1][location.second+2]=true, children.emplace_back(make_pair(location.first+1,location.second+2)); if(location.first-1>=0 && location.second+2<=n-1 && !board[location.first-1][location.second+2]) moveNames.emplace_back("LL"), board[location.first-1][location.second+2]=true, children.emplace_back(make_pair(location.first-1,location.second+2)); if(location.first-2>=0 && location.second-0>=0 && !board[location.first-2][location.second-0]) moveNames.emplace_back("L"), board[location.first-2][location.second-0]=true, children.emplace_back(make_pair(location.first-2,location.second-0)); } pair location; }; int main() { //ios::sync_with_stdio(0), cin.tie(0); bool test= false; if(test) freopen("/Users/aj/code/HackerRank/input.txt", "r", stdin); int xs,ys,xe,ye; cin>>n>>ys>>xs>>ye>>xe; deque dq; node* root=new node(NULL,pair(xs,ys)); root->addChildren(); board[xs][ys]=true; dq.emplace_back(root); bool endfound=false; node* thenode=NULL; while(dq.size()>0 && !endfound){ node* curnode=dq.front(); dq.pop_front(); for(int i=0;ichildren.size();i++){ pair clocation=curnode->children[i]; thenode=new node(curnode,clocation); thenode->addChildren(); if(clocation.first==xe && clocation.second==ye){ endfound=true; break; } dq.emplace_back(thenode); } } if(!endfound)cout<<"Impossible"; else{ vector path; while(thenode->parent!=NULL){ node* pr=thenode->parent; pair curloc=thenode->location; for(int c=0;cchildren.size();c++){ pair childloc=pr->children[c]; if(curloc.first==childloc.first && curloc.second==childloc.second){ path.emplace_back(pr->moveNames[c]); break; } } thenode=thenode->parent; } reverse(path.begin(),path.end()); cout<