#include using namespace std; struct knight { int x; int y; int d; string path; }; bool check(int a,int b,int n) { if(a<0 || b<0 || a>=n || b>=n) return false; return true; } int visit[200][200]={1,1}; knight k; stackmystack; void go(int kx,int ky,int d,int n) { if(check(kx-2,ky-1,n) && visit[kx-2][ky-1]) { k.x=kx-2; k.y=ky-1; k.d=d+1; k.path="UL"; mystack.push(k); visit[kx-2][ky-1]=0; } if(check(kx-2,ky+1,n) && visit[kx-2][ky+1]) { k.x=kx-2; k.y=ky+1; k.d=d+1; k.path="UR"; mystack.push(k); visit[kx-2][ky+1]=0; } if(check(kx,ky+2,n) && visit[kx][ky+2]) { k.x=kx; k.y=ky+2; k.d=d+1; k.path="R"; mystack.push(k); visit[kx][ky+2]=0; } if(check(kx+2,ky+1,n) && visit[kx+2][ky+1]) { k.x=kx+2; k.y=ky+1; k.d=d+1; k.path="LR"; mystack.push(k); visit[kx+2][ky+1]=0; } if(check(kx+2,ky-1,n)&& visit[kx+2][ky-1]) { k.x=kx+2; k.y=ky-1; k.d=d+1; k.path="LL"; mystack.push(k); visit[kx+2][ky-1]=0; } if(check(kx,ky-2,n) && visit[kx][ky-2]) { k.x=kx; k.y=ky-2; k.d=d+1; k.path="L"; mystack.push(k); visit[kx][ky-2]=0; } return ; } void printShortestPath(int n, int kx, int ky, int xn, int yn) { visit[kx][ky]=0; if(kx== xn && ky==yn) { cout<<0; return; } else { if(check(kx-2,ky-1,n) && visit[kx-2][ky-1]) { k.x=kx-2; k.y=ky-1; k.d=1; k.path="UL"; mystack.push(k); visit[kx-2][ky-1]=0; } if(check(kx-2,ky+1,n) && visit[kx-2][ky+1]) { k.x=kx-2; k.y=ky+1; k.d=1; k.path="UR"; mystack.push(k); visit[kx-2][ky+1]=0; } if(check(kx,ky+2,n) && visit[kx][ky+2]) { k.x=kx; k.y=ky+2; k.d=1; k.path="R"; mystack.push(k); visit[kx][ky+2]=0; } if(check(kx+2,ky+1,n) && visit[kx+2][ky+1]) { k.x=kx+2; k.y=ky+1; k.d=1; k.path="LR"; mystack.push(k); visit[kx+2][ky+1]=0; } if(check(kx+2,ky-1,n)&& visit[kx+2][ky-1]) { k.x=kx+2; k.y=ky-1; k.d=1; k.path="LL"; mystack.push(k); visit[kx+2][ky-1]=0; } if(check(kx,ky-2,n) && visit[kx][ky-2]) { k.x=kx; k.y=ky-2; k.d=1; k.path="L"; mystack.push(k); visit[kx][ky-2]=0; } vectorpa; while(!mystack.empty()) { k=mystack.top(); mystack.pop(); strcpy(pa[k.d-1],k.path); if(k.x==xn && k.y==yn) { 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; }