moonlightshadow123
5/30/2017 - 3:04 PM

63. Unique Paths II

  1. Unique Paths II
class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        mat = [[0 for _ in range(n+1)] for _ in range(m+1)]
        # mat[i][j] represents the number of ways for (i+,j+1) to (m,n),
        # so mat[m-1][n-1] = 1
        for i in range(m-1,-1,-1):
            for j in range(n-1,-1,-1):
                if obstacleGrid[i][j] == 1:
                    mat[i][j] = 0
                elif i == m-1 and j == n-1:
                    mat[i][j] = 1
                else:
                    mat[i][j] = mat[i+1][j] + mat[i][j+1]
        return mat[0][0]

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

Follow up for "Unique Paths":

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example, There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2.