Be a knight. Apply the BFS!


#1
// Created By : Pranav Singhal
// IIIT-Allahabad
bool check(int i,int j,int A,int B){
    return (i<A && i>=0 && j<B && j>=0);
}
int dx[8]={-2,-1,1,2,2,1,-1,-2}; // the eight moves of knight in dx and dy together
int dy[8]={-1,-2,-2,-1,1,2,2,1};
map<pair<int,int>,int> vis;
int Solution::knight(int A, int B, int C, int D, int E, int F) {
    vis.clear();
    C--,D--,E--,F--;
    if(C==E && D==F) return 0;
    queue<pair<int,pair<int,int> > > q;
    q.push({0,{C,D}});
    while(!q.empty()){   // bfs for all possible moves
        int i=q.front().second.first,j=q.front().second.second;
        int lev=q.front().first;
        q.pop();
        for(int k=0;k<8;k++){
            int x=i+dx[k],y=j+dy[k];
            if(check(x,y,A,B) && vis[{x,y}]==0){
                if(x==E && y==F) return lev+1;
                vis[{x,y}]=1;
                q.push({lev+1,{x,y}});
            }
        }
    }
    return -1;
}