red knight problem

red_knight_problem.cpp

#include<bits/stdc++.h>
using namespace std;
#define lli long long int
#define ulli unsigned long long int
#define ll long long 
#define ull  unsigned long long
#define mp make_pair
#define s(n)   scanf("%d",&n)
#define sc(n)  scanf("%c",&n)
#define sl(n)  scanf("%lld",&n)
#define sf(n)  scanf("%lf",&n)
#define ss(n)  scanf("%s",n)
#define p(n)   printf("%d",n)
#define pc(n)  printf("%c",n)
#define pl(n)  printf("%lld",n)
#define pf(n)  printf("%lf",n)
#define ps(n)  printf("%s",n)
#define pn printf("\n")
#define space printf(" ")
#define loopf(X,Y) for(int i=X;i<Y;i++)
#define loopb(X,Y) for(int i=X;i>Y;i--)
#define dout(X) if(X)
#define matrix(rowsize,colsize,type,name) vector<vector<(type)>> name((rowsize),vector<(type)>(colsize));
struct ppair{
        int x,y;
        ppair(){};
        ppair(int _x,int _y){
                x=_x,y=_y;
        }
};
struct pos{
        int x,y,moves;
        pos(){};
        pos(int _x,int _y,int _moves){
                x=_x,y=_y,moves=_moves;
        }
};
bool isInside(int x,int y,int n){
        if(x<0 || x>n-1 || y<0 || y>n-1)
                return false;
        return true;
}
int myValue(int x,int y, int n){
        int val=(n)*(x%n)+y%n;
        return val;
}
ppair whoIs(int val,int n){
        int x=val/n;
        int y=val-n*x;
        ppair ret(x,y);
        return ret;
}
string step(int x,int y){
        string ret;
        if(x==1 && y==-2)
                ret="LL";
        else if(x==-1 && y==-2)
                ret="LR";
        else if(x==1 && y==2)
                ret="UL";
        else if(x==2 && y==0)
                ret="L";
        else if(x==-2 && y==0)
                ret="R";
        else if(x==-1 && y==2)
                ret="UR";
        return ret;
}
int printShortestPath(int si,int sj,int ei,int ej,int n,vector<string> & final_vect){
        queue<pos> q;
        vector<int> vect[n];
        int dx[]={-1,1,2,1,-1,-2};
        int dy[]={-2,-2,0,2,2, 0};
        int visit[n][n],val=0,start_val=myValue(si,sj,n);
        for(int i=0;i<n;i++)
                for(int j=0;j<n;j++){
                        visit[i][j]=0;
			vect[i].push_back(-1);
		}
        visit[si][sj]=1;
        vect[si][sj]=-1;
        q.push(pos(si,sj,0));
        pos cur;
        while(!q.empty()){
                cur=q.front();
                dout(0) p(cur.x),space,p(cur.y),space,p(cur.moves),pn;
                q.pop();
                if(cur.x==ei && cur.y==ej){
                        int temp=myValue(cur.x,cur.y,n);
                        ppair ttemp=whoIs(temp,n);
                        ppair rem;
                        while(temp!=start_val){
                                rem=ttemp;
                                int ans_cal=vect[ttemp.x][ttemp.y];
                                ttemp=whoIs(ans_cal,n);
                                temp=ans_cal;
                                int diffx=ttemp.x-rem.x,diffy=ttemp.y-rem.y;
                                final_vect.push_back(step(diffx,diffy));
                        }
                        return cur.moves;
                }
                for(int i=0;i<6;i++){
                        int new_x=cur.x+dx[i],new_y=cur.y+dy[i];
                        if(isInside(new_x,new_y,n) && !visit[new_x][new_y]){
                                        q.push(pos(new_x,new_y,cur.moves+1));
                                        vect[new_x][new_y]=myValue(cur.x,cur.y,n);
                                        visit[new_x][new_y]=1;
                        }
                }
        }
        return 0;
}
int main(){
        int si,sj,ei,ej,n;
        s(n);
        s(si),s(sj),s(ei),s(ej);
        vector<string> final_vect;
        int val=0;
        int ans=printShortestPath(sj,si,ej,ei,n,final_vect);
        if(!ans) ps("Impossible"),pn;
        else   {
                p(ans),pn;
                for(int i=final_vect.size()-1;i>=0;i--)
                        cout<<final_vect[i],space;
                pn;
        }
        return 0;
}