Most Readable and clear [cpp] [bfs]


#1
bool isValid(int x, int y, int row, int col){
    if(x < 0 || y < 0 || x >= row || y >= col)return false;
    return true;
}
//  If reachable position is not already visited and is inside the board, we push this state into queue with distance 1 more than its parent state.
int Solution::knight(int row, int col, int x, int y, int t1, int t2) {
    
    // all the 8 direction
    int dx[8] = {-1, 1, 2, 2, 1, -1, -2, -2};
    int dy[8] = {2, 2, 1, -1, -2, -2, -1, 1};
    
    x--,y--,t1--,t2--;
    vector<vector<bool>>visited(row, vector<bool>(col, false));
    queue<vector<int>>q;
    q.push({x, y, 0}); // {ith coord, jth coord, depth}
    visited[x][y] = true;
    while(!q.empty()){
        vector<int>p = q.front(); q.pop();
        int xx = p[0];
        int yy = p[1];
        int count = p[2];
        if(xx == t1 && yy == t2)return count;
        // push all possible next position of knight(at max 8)
        for(int i = 0; i < 8; ++i){
            int x = xx + dx[i];
            int y = yy + dy[i];
            
            if(isValid(x, y, row, col) && !visited[x][y]){
                // cout<<x<<" "<<y<<endl;
                visited[x][y] = true;
                q.push({x, y, count+1});
            }
        }
    }
    return -1;
}