int bfsmove(int **board,int N,int M,int starti,int startj,int endi,int endj){
queue<pair<int,int> > q;
//Use this directional additives to help you chose the directions
//This will help you in avoiding writing 8 if-else conditions
vector <vector <int> > dir={{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2}};
//Level vector to store the shortest distance traveled so far
vector <vector<int> > lev(N,vector<int>(M,0));
q.push(make_pair(starti,startj));
board[starti][startj]=1;
while(!q.empty()){
pair<int,int> p=q.front();
q.pop();
for(int i=0;i<8;i++){
int newr=p.first+dir[i][0];
int newc=p.second+dir[i][1];
if(newr>=0 && newr<N && newc>=0 && newc<M && !board[newr][newc]){
lev[newr][newc]=lev[p.first][p.second]+1;
board[newr][newc]=1;
q.push(make_pair(newr,newc));
if(newr==endi && newc==endj)
return lev[endi][endj];
}
}
}
return -1; //Return -1 if endi and endj are never encountered
}
int Solution::knight(int A, int B, int C, int D, int E, int F) {
if(C==E && D==F)
return 0;
int **board=new int*[A];
for(int i=0;i<A;i++){
board[i]=new int[B];
for(int j=0;j<B;j++){
board[i][j]=0;
}
}
//BFS is used here as we need to reach the shortest path as soon as possible
int ans=bfsmove(board,A,B,C-1,D-1,E-1,F-1);//C,D,E and F are orignally 1 based converting to them 0 based
return ans;
}