Paths Around the Puddles
yard is a grid in which 0 marks dry ground and 1 marks a puddle. You start in the top left cell and walk to the bottom right cell, moving one cell right or one cell down at a time, and you may never step into a puddle. Return the number of different dry routes from the start to the end. If the start or the end is a puddle, return 0. A grid with a single dry cell has exactly one route: stay where you are.
Example 1
yard [[0,0,0],[0,1,0],[0,0,0]]
returns 2
You can pass the puddle along the top and right edges or along the left and bottom edges.
Example 2
yard [[0,1],[0,0]]
returns 1
The top right cell is a puddle, so the only route is down and then right.
Constraints
1 <= rows, cols <= 10yard[r][c]is0or1- Every row of
yardhas the same length
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Dynamic programming problems
- Rabbit PairsEasy
- Ribbon for SaleEasy
- Three Step StairsEasy
- Tiling a Two by N StripEasy
- Token Orders at the TurnstileEasy
- Two-Lane RoadEasy
- Best Stretch SumMedium
- Cheapest DescentMedium