Count Grid Routes Around Obstacles
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
The rectangular integer grid `blocked` uses `0` for an open cell and `1` for an obstacle. A route begins at the upper-left cell and ends at the lower-right cell. Each move goes one cell to the right or one cell down.
Count the routes whose cells are all open, including their starting and ending cells. Return `0` when no such route exists. The answer for any supplied grid is at most `2 * 10^9`.
### Examples
**Example 1**
```text
Input: blocked = [[0,0,0,0],[0,1,0,0]]
Output: 2
```
A route must enter the bottom row in column `2` or column `3`; entering earlier would encounter the obstacle.
**Example 2**
```text
Input: blocked = [[1,0],[0,0]]
Output: 0
```
The starting cell is blocked, so no route is permitted.
### Constraints
- The number of rows and the number of columns are each between `1` and `100`, inclusive.
- Every row has the same number of entries.
- Each entry of `blocked` is `0` or `1`.
- The number of valid routes is at most `2 * 10^9`.
Overview: Count right-and-down routes through an obstacle grid while rejecting blocked cells, including blocked endpoints and grids with no valid route.
