#include #define mp make_pair using namespace std; bool check(int i,int j,int n) { if(i>=0 && j>=0 && i , pair >par; queue< pair< pair,int> >q; q.push(mp(mp(is,js),0)); v[is][js]=true; par[mp(is,js)]=mp(-1,-1); while(!q.empty()) { pair< pair,int>p; p=q.front(); q.pop(); pairpp; pp=p.first; int i=pp.first; int j=pp.second; int an=p.second; if(i==ie && j==je) { ans=an; break;//UL, UR, R, LR, LL, L } if(check(i-2,j-1,n) && v[i-2][j-1]==false) { q.push(mp(mp(i-2,j-1),an+1)); v[i-2][j-1]=true; par[mp(i-2,j-1)]=mp(i,j); } if(check(i-2,j+1,n) && v[i-2][j+1]==false) { q.push(mp(mp(i-2,j+1),an+1)); v[i-2][j+1]=true; par[mp(i-2,j+1)]=mp(i,j); } if(check(i,j+2,n) && v[i][j+2]==false) { q.push(mp(mp(i,j+2),an+1)); v[i][j+2]=true; par[mp(i,j+2)]=mp(i,j); } if(check(i+2,j+1,n) && v[i+2][j+1]==false) { q.push(mp(mp(i+2,j+1),an+1)); v[i+2][j+1]=true; par[mp(i+2,j+1)]=mp(i,j); } if(check(i+2,j-1,n) && v[i+2][j-1]==false) { q.push(mp(mp(i+2,j-1),an+1)); v[i+2][j-1]=true; par[mp(i+2,j-1)]=mp(i,j); } if(check(i,j-2,n) && v[i][j-2]==false) { q.push(mp(mp(i,j-2),an+1)); v[i][j-2]=true; par[mp(i,j-2)]=mp(i,j); } } if(ans>0) { cout<s; pairsr,en; sr=mp(is,js); en=mp(ie,je); //s.push(en); while(en!=sr) { //s.push(par[en]); //en=par[en]; if(en.first-par[en].first==0) { if(en.second-par[en].second==2) s.push("R"); else s.push("L"); } else if(en.first-par[en].first==2) { if(en.second-par[en].second==1) s.push("LR"); else s.push("LL"); } else { if(en.second-par[en].second==1) s.push("UR"); else s.push("UL"); } en=par[en]; } while(!s.empty()) { string str=s.top(); s.pop(); 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; }