33. Knight On Chess Board

Given any source point, (C, D) and destination point, (E, F) on a chess board, we need to find whether Knight can move to the destination or not.

Knight's movements on a chess board

The above figure details the movements for a knight ( 8 possibilities ).

If yes, then what would be the minimum number of steps for the knight to move to the said point. If knight can not move from the source point to the destination point, then return -1.

Note: A knight cannot go out of the board.

Input Format:

The first argument of input contains an integer A.
The second argument of input contains an integer B.
    => The chessboard is of size A x B.
The third argument of input contains an integer C.
The fourth argument of input contains an integer D.
    => The Knight is initially at position (C, D).
The fifth argument of input contains an integer E.
The sixth argument of input contains an integer F.
    => The Knight wants to reach position (E, F).

Output Format:

If it is possible to reach the destination point, return the minimum number of moves.
Else return -1.

Constraints:

1 <= A, B <= 500

Example

Input 1:
    A = 8
    B = 8
    C = 1
    D = 1
    E = 8
    F = 8
    
Output 1:
    6

Explanation 1:
    The size of the chessboard is 8x8, the knight is initially at (1, 1) and the knight wants to reach position (8, 8).
    The minimum number of moves required for this is 6

Solution: (BFS)

bool isValid(int x, int y, int n, int m)
{
    if (x >= n || x < 0)
    {
        return false;
    }

    if (y >= m || y < 0)
    {
        return false;
    }

    return true;
}

int bfs(vector<int> &dx, vector<int> &dy, int n, int m, int startx, int starty, int endx, int endy, vector<vector<bool>> &vs)
{
    queue<pair<int, int>> q;
    queue<int> dist;

    q.push({startx, starty});
    dist.push(0);

    vs[startx][starty] = true;

    while (!q.empty())
    {

        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        int res = dist.front();
        dist.pop();

        if (x == endx && y == endy)
        {
            return res;
        }

        for (int i = 0; i < 8; i++)
        {
            if (isValid(x + dx[i], y + dy[i], n, m) && !vs[x + dx[i]][y + dy[i]])
            {
                q.push({x + dx[i], y + dy[i]});
                dist.push(res + 1);
                vs[x + dx[i]][y + dy[i]] = true;
            }
        }
    }

    return -1;
}

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

    vector<int> dx{-1, -1, -2, -2, 1, 1, 2, 2};
    vector<int> dy{-2, 2, -1, 1, 2, -2, 1, -1};
    vector<vector<bool>> vs(A, vector<bool>(B, false));

    return bfs(dx, dy, A, B, C - 1, D - 1, E - 1, F - 1, vs);
}