# Easy solution using BFS in C++

#1
``````void make_neighbor(int m, int n, vector<pair<int,int>> &neighbor, pair<int,int> p){

int x[]={+2,+2,+1,+1,-1,-1,-2,-2};
int y[]={+1,-1,+2,-2,+2,-2,+1,-1};

for(int i=0;i<=7;i++){
int x_cord = p.first+x[i];
int y_cord = p.second+y[i];
if(x_cord>=0 and x_cord<m and y_cord>=0 and y_cord<n)
neighbor.push_back(make_pair(x_cord,y_cord));
}
``````

}

int bfs(int m, int n, int sx, int sy, int dx, int dy){

``````vector<vector<int>> visited(m,vector<int>(n, 0));
vector<vector<int>> distance(m,vector<int> (n, INT_MAX));
queue<pair<int,int>> q;

visited[sx][sy]=1;
distance[sx][sy]=0;
q.push(make_pair(sx,sy));

while(!q.empty()){

pair<int,int> p = q.front();
q.pop();

vector<pair<int,int>> neighbor;
make_neighbor(m,n,neighbor,p);

for(int i=0;i<neighbor.size();i++){
int x = neighbor[i].first;
int y = neighbor[i].second;
if(visited[x][y]==0){
visited[x][y]=1;
distance[x][y]=distance[p.first][p.second]+1;
q.push(neighbor[i]);
}
if(neighbor[i]==make_pair(dx,dy))
return distance[x][y];
}
}
return -1;
``````

}

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

``````if(C==E and D==F)
return 0;

int path_length = bfs(A,B,C-1,D-1,E-1,F-1);
return path_length;
``````

}

#2

Edited your code a bit. This one consumes less memory.

``````void make_neighbor(int m, int n, vector<pair<int,int>> &neighbor, pair<int,int> p){
int x[]={+2,+2,+1,+1,-1,-1,-2,-2};
int y[]={+1,-1,+2,-2,+2,-2,+1,-1};

for(int i=0;i<=7;i++){
int x_cord = p.first+x[i];
int y_cord = p.second+y[i];
if(x_cord>=0 and x_cord<m and y_cord>=0 and y_cord<n)
neighbor.push_back(make_pair(x_cord,y_cord));
}
}

int bfs(int m, int n, int sx, int sy, int dx, int dy){
vector<vector<int>> visited(m,vector<int>(n, 0));
queue<pair<int,int>> q;

q.push(make_pair(sx,sy));

while(!q.empty()){

pair<int,int> p = q.front();
q.pop();

vector<pair<int,int>> neighbor;
make_neighbor(m,n,neighbor,p);

for(int i=0;i<neighbor.size();i++){
int x = neighbor[i].first;
int y = neighbor[i].second;
if(visited[x][y]==0){
visited[x][y]=visited[p.first][p.second]+1;
q.push(neighbor[i]);
}
if(neighbor[i]==make_pair(dx,dy))
return visited[x][y];
}
}
return -1;
}

int Solution::knight(int A, int B, int C, int D, int E, int F) {
if(C==E and D==F)
return 0;
int path_length = bfs(A,B,C-1,D-1,E-1,F-1);
return path_length;
}``````