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