Unique Paths II

Given a nonempty rectangular matrix of 0s and 1s, return the number of paths from its top-left cell to its bottom-right cell. A 0 is open and a 1 is blocked.…

Given a nonempty rectangular matrix of 0s and 1s, return the number of paths from its top-left cell to its bottom-right cell. A 0 is open and a 1 is blocked. Move only one cell right or one cell down, never through a blocked cell. A blocked start or destination yields zero paths.

- 1 <= number of rows, number of columns <= 100. - Every cell is the integer 0 or 1; the matrix is rectangular. - The final number of paths is guaranteed to be at most 1,000,000,000. Intermediate counts in regions cut off from the destination may be larger. - Visualizer presets use matrices at most 8 by 8; larger valid inputs are coding-only.

Example 1: input matrix = [[0,0,0],[0,1,0],[0,0,0]]; output 2. Only the routes around the central obstacle survive.

Example 2: input matrix = [[0,0,0],[0,0,1],[0,1,0]]; output 0. Both possible predecessors of the destination are blocked.

Category: Arrays. Topic: dynamic-programming. Difficulty: medium. Patterns: dynamic-programming, dynamic-programming-2d.