2912. Number of Ways to Reach Destination in the Grid

We are asked to count the number of sequences of length k + 1 that start from (xs, ys) and end with (xd, yd). i.e., (xs, ys), (x1, y1), ..., (xk - 1, yk - 1), (xd, yd).

The key point is to see x and y separately.

Suppose we do i vertical moves and k - i horizontal moves.

In each vertical move, we change only y. Now let's count the number of sequences of length i + 1 that start with source[2] and end with dest[2]. Let's call this number vertical_count.

Do the same for horizontal moves and let it be horizontal_count.

For each i, the number of ways would be vertical_count * horizontal_count * C(n, i) since the order of vertical and horizontal moves could be arbitrary.