Simple BFS solution in C++

interview-questions
Tags: #<Tag:0x00007f18243a1bd0>

#1

int Solution::knight(int A, int B, int C, int D, int E, int F) {

vector<vector<int>> minhops(A,vector<int>(B,INT_MAX));
minhops[C-1][D-1]=0;

queue<pair<int,int>> q;
q.push(make_pair(C-1,D-1));

while(!q.empty())
{
    pair<int,int> currpos=q.front();
    q.pop();
    if(currpos==make_pair(E-1,F-1))
    return minhops[E-1][F-1];
    
    int i=currpos.first;
    int j=currpos.second;

//Check for all possible positions that the knoght can move next.
if(i+2<A && j+1<B && minhops[i+2][j+1]>minhops[i][j]+1)
{
minhops[i+2][j+1]=minhops[i][j]+1;
q.push(make_pair(i+2,j+1));
}
if(i+2<A && j-1>=0 && minhops[i+2][j-1]>minhops[i][j]+1)
{
minhops[i+2][j-1]=minhops[i][j]+1;
q.push(make_pair(i+2,j-1));
}
if(i-2>=0 && j+1<B && minhops[i-2][j+1]>minhops[i][j]+1)
{
minhops[i-2][j+1]=minhops[i][j]+1;
q.push(make_pair(i-2,j+1));
}
if(i-2>=0 && j-1>=0 && minhops[i-2][j-1]>minhops[i][j]+1)
{
minhops[i-2][j-1]=minhops[i][j]+1;
q.push(make_pair(i-2,j-1));
}
if(i+1<A && j+2<B && minhops[i+1][j+2]>minhops[i][j]+1)
{
minhops[i+1][j+2]=minhops[i][j]+1;
q.push(make_pair(i+1,j+2));
}
if(i+1<A && j-2>=0 && minhops[i+1][j-2]>minhops[i][j]+1)
{
minhops[i+1][j-2]=minhops[i][j]+1;
q.push(make_pair(i+1,j-2));
}
if(i-1>=0 && j+2<B && minhops[i-1][j+2]>minhops[i][j]+1)
{
minhops[i-1][j+2]=minhops[i][j]+1;
q.push(make_pair(i-1,j+2));
}
if(i-1>=0 && j-2>=0 && minhops[i-1][j-2]>minhops[i][j]+1)
{
minhops[i-1][j-2]=minhops[i][j]+1;
q.push(make_pair(i-1,j-2));
}
}

return -1;

}