1
# Runtime: 75 ms (Top 36.49%) | Memory: 14 MB (Top 43.32%)
2
class Solution:
3
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
4
        def valid(r, c, matrix):
5
            return r >= 0 and c >= 0 and r < len(matrix) and c < len(matrix[0])
6

7
        dp = [[0] * len(obstacleGrid[0]) for _ in range(len(obstacleGrid))]
8
        dp[0][0] = 1 ^ obstacleGrid[0][0]
9

10
        for r in range(len(obstacleGrid)):
11
            for c in range(len(obstacleGrid[0])):
12
                if obstacleGrid[r][c] != 1:
13
                    if valid(r - 1, c, dp) and obstacleGrid[r - 1][c] != 1:
14
                        dp[r][c] += dp[r - 1][c]
15
                    if valid(r, c - 1, dp) and obstacleGrid[r][c - 1] != 1:
16
                        dp[r][c] += dp[r][c - 1]
17

18
        return dp[-1][-1]