Unique Paths with Obstacles

Problem

Count the paths from the top-left to the bottom-right of a grid moving only right or down, where cells containing 1 are obstacles that cannot be entered.

Use dynamic programming with dp[0][0] = 1 and zeroing every obstacle cell as you sweep. If the start or end cell is blocked, return 0.

Hint

An obstacle contributes zero paths; everything else is the sum of paths from above and from the left.

Test cases

case 1

in: [[[0,0,0],[0,1,0],[0,0,0]]]

expected: 2

case 2

in: [[[0,1],[0,0]]]

expected: 1

case 3

in: [[[1]]]

expected: 0

case 4

in: [[[0]]]

expected: 1

case 5

in: [[[0,0],[0,0]]]

expected: 2

case 6

in: [[[0,0],[1,0]]]

expected: 1

Starter codePython

def unique_paths_with_obstacles(grid):
    # Your code here
    pass

6 test cases · run your code against them in the editor