### Problem

Given a 2D array A[M][N], aka Grid / Maze / Matrix

Write an algorithm to count the number of unique paths to reach to A[M-1][N-1] from A[0][0]

At any cell (x, y), you can either go to (x+1, y) or (x, y+1) if there's no obstacle

### Example

Input `A[3][3]`

with values `{{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}`

, 0 and 1 represent for empty and obstacle respectively

Expected output `2`

### Approach

Using dynamic programming bottom-up

- Fill up matrix
`cache[i][j]`

to count unique paths to`(i,j)`

`cache[i][j] = cache[i-1][j] + cache[i][j-1]`

for each`(i,j)`

with`A[i][j]`

as 0`cache[0][0] = 1`

,`cache[i][0]`

and`cache[0][j]`

are base cases`cache[rows-1][cols-1]`

is final result

### Implementation

```
```