Fork me on GitHub

Unique Paths II

Posted on

Description

https://leetcode.com/problems/unique-paths-ii/description/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        if obstacleGrid is None or len(obstacleGrid) == 0:
            return 0
        
        ret = [ [0 for i in range(len(obstacleGrid[0]))] for j in range(len(obstacleGrid)) ]
        
        for i in range(len(obstacleGrid[0])):
            if obstacleGrid[0][i] == 0:
                ret[0][i] = 1
            else:
                break
            
        for j in range(len(obstacleGrid)):
            if obstacleGrid[j][0] == 0:
                ret[j][0] = 1
            else:
                break
        
        for i in range(1, len(obstacleGrid)):
            for j in range(1, len(obstacleGrid[0])):
                if obstacleGrid[i][j] == 0:
                    left  = (0 if obstacleGrid[i][j - 1] == 1 else ret[i][j - 1])     
                    up = (0 if obstacleGrid[i - 1][j] == 1 else ret[i - 1][j])
                    ret[i][j] = left + up
        
        return ret[-1][-1]