Count Right/Down Routes Across a Grid With Blocked Cells
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
A robot starts in the top-left cell of an `m x n` grid and wants to reach the bottom-right cell. Each move takes it exactly one cell to the right or one cell down. Some cells are blocked: `grid[r][c] == 1` marks a blocked cell the robot can never enter, and `grid[r][c] == 0` marks an open cell. Return the number of distinct routes from the start cell `(0, 0)` to the target cell `(m - 1, n - 1)`. Two routes are distinct when their sequences of moves differ.
### Function Signature
```python
def count_routes(grid: list[list[int]]) -> int:
```
### Rules
- If the start cell or the target cell is blocked, the answer is `0`.
- If the grid is a single open cell, the start is the target and there is exactly `1` route, with no moves.
- The robot can never leave the grid.
### Constraints
- `1 <= m, n <= 100`, where `m = len(grid)` and `n = len(grid[0])`; every row has length `n`.
- Every cell is `0` or `1`.
- Test grids are chosen so that, for every open cell, the number of routes from the start to that cell and the number of routes from that cell to the target are each at most `2 * 10^9`. In particular, the answer fits in a signed 32-bit integer.
### Examples
**Example 1**
```text
Input: grid = [[0, 0, 0, 0],
[0, 1, 0, 0],
[0, 0, 0, 1],
[0, 0, 0, 0]]
Output: 4
```
With `R` for a move right and `D` for a move down, the four routes that avoid the blocked cells `(1, 1)` and `(2, 3)` are `RRDDDR`, `DDRRDR`, `DDRDRR` and `DDDRRR`.
**Example 2**
```text
Input: grid = [[0, 1],
[1, 0]]
Output: 0
```
Both cells next to the start are blocked, so the target cannot be reached.
**Example 3**
```text
Input: grid = [[0]]
Output: 1
```
Overview: A coding problem that counts the routes from the top-left to the bottom-right cell of a grid when every move goes right or down and some cells are blocked. It tests systematic path counting on grids and edge cases such as a blocked start or target, a single-cell grid, or no open route at all.
Read the full Meta Software Engineer interview experience this question came from