No of ways to walk M steps in a grid

Question

You are situated in an grid at position x,y. The dimensions of the row is dx,dy. In one step, you can walk one step ahead or behind in the row or the column. In how many ways can you take M steps such that you do not leave the grid at any point ?
You can visit the same position more than once.
You leave the grid if you for any x,y either x,y <= 0 or x,y > dx,dy.
1 <= M <= 300
1 <= x,y <= dx,dy <= 100

Input:
M
x y
dx dy

Output:
no of ways

Example:
Input:
1
6 6
12 12

Output:
4

Example:
Input:
2
6 6
12 12

Output:
16
If you are at position 6,6 then you can walk to (6,5),(6,7),(5,6),(7,6).

I am stuck at how to use Pascal's Triangle to solve it.Is that the correct approach? I have already tried brute force but its too slow.

C[i][j], Pascal Triangle
C[i][j] = C[i - 1][j - 1] + C[i - 1][j]

T[startpos][stp]
T[pos][stp] = T[pos + 1][stp - 1] + T[pos - 1][stp - 1]

Answer 1

You can solve 1d problem with the formula you provided.

Let H[pos][step] be number of ways to move horizontal using given number of steps.
And V[pos][step] be number of ways to move vertical sing given number of steps.

You can iterate number of steps that will be made horizontal i = 0..M
Number of ways to move so is H[x][i]*V[y][M-i]*C[M][i], where C is binomial coefficient.

You can build H and V in O(max(dx,dy)*M) and do second step in O(M).

EDIT: Clarification on H and V. Supppose that you have line, that have d cells: 1,2,...,d. You're standing at cell number pos then T[pos][step] = T[pos-1][step-1] + T[pos+1][step-1], as you can move either forward or backward.

Base cases are T[0][step] = 0, T[d+1][step] = 0, T[pos][0] = 1.

We build H assuming d = dx and V assuming d = dy.

EDIT 2: Basically, the idea of algorithm is since we move in one of 2 dimensions and check is also based on each dimension independently, we can split 2d problem in 2 1d problems.