Unique Paths II — LeetCode 63 Python Solution

The problem

You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]).

Example

Input

obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]

Output

2

Explanation

There is one obstacle in the middle of the 3x3 grid above.

Python solution

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        @cache
        def dfs(i: int, j: int) -> int:
            if i >= m or j >= n or obstacleGrid[i][j]:
                return 0
            if i == m - 1 and j == n - 1:
                return 1
            return dfs(i + 1, j) + dfs(i, j + 1)

        m, n = len(obstacleGrid), len(obstacleGrid[0])
        return dfs(0, 0)

Complexity

Pattern: Matrix and Grid

Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 63. Unique Paths II is filed here because LeetCode tags it Matrix, which is the vocabulary this hub collects.

The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.

Related problems