/************************************ * AUTHOR: Divyansh Gaba * * INSTITUTION: ASET, BIJWASAN * ************************************/ #include #define fast ios_base::sync_with_stdio(0); cin.tie(0); #define F first #define S second #define PB push_back #define MP make_pair #define REP(i,a,b) for (int i = a; i <= b; i++) using namespace std; typedef long long ll; typedef vector vi; typedef pair pi; int dx[]={-2,-2,+0,+2,+2,+0}; int dy[]={-1,+1,+2,+1,-1,-2}; string s[]={"UL","UR","R","LR","LL","L"}; const int moves = 6; const int N = 201; const int INF = 1e9; int n; bool valid(int x,int y) { if(x<0||y<0||x>=n||y>=n) return false; return true; } pi st,en; int parent[N][N]; vector> dist(N,vector(N,INF)); int bfs(int x,int y) { memset(parent,~0,sizeof(parent)); dist[x][y]=0; vector> vis(n,vector(n,false)); priority_queue,vector>,greater>> p; p.push({0,{x,y}}); while(!p.empty()) { auto u = p.top(); p.pop(); if(vis[u.S.F][u.S.S]) continue; vis[u.S.F][u.S.S]=true; for(int i = 0;i=dist[u.S.F][u.S.S]+1&&parent[xi][yi]>n; cin>>st.F>>st.S; cin>>en.F>>en.S; int ans = bfs(st.F,st.S); if(ans!=INF) { cout< st; int x = en.F,y=en.S; while(parent[x][y]!=-1) { int i = parent[x][y]; x = x-dx[i]; y = y-dy[i]; st.push(i); } while(!st.empty()) cout<