Unique Paths II
Medium · dynamic programming
A garden is laid out as a rectangular grid. Each cell is either free (0) or holds a rock (1).
A snail starts in the top-left cell and wants to reach the bottom-right cell. On every move it goes one cell down or one cell right, never up or left, it must stay inside the garden, and it can never enter a cell with a rock.
Return the number of different routes from the top-left cell to the bottom-right cell, modulo 10^9 + 7. Two routes are different if they visit a different sequence of cells. If a rock sits on the start or the finish cell, or no route exists, return 0.
Examples
Example 1
Input: grid = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
Output: 2
The rock in the middle blocks every route through the centre. Only the route hugging the top and right edges and the route hugging the left and bottom edges remain.
Example 2
Input: grid = [[0, 0], [0, 0]]
Output: 2
With no rocks it is a plain 2 by 2 garden: down then right, or right then down.
Example 3
Input: grid = [[0, 1], [0, 0]]
Output: 1
The rock cuts off the route through the top-right cell, leaving only down then right.
Constraints
- 1 <= len(grid), len(grid[0]) <= 100
- Every row of grid has the same length.
- grid[i][j] is 0 or 1.