# BFS based solution with directional additives

#1

int bfsmove(int **board,int N,int M,int starti,int startj,int endi,int endj){

``````queue<pair<int,int> > q;

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;
``````

}