FunctionRacerProblemsRace

Paths Around the Puddles

EasyDynamic programmingPython, JavaScript, TypeScript, Java, C++

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

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Dynamic programming problems