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.
Notice
m and n will be at most 100.
Example
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]
]
Solution
class Solution:
"""
@param obstacleGrid: An list of lists of integers
@return: An integer
"""
def uniquePathsWithObstacles(self, obstacleGrid):
# write your code here
if obstacleGrid[0][0] == 1:
return 0
m, n = len(obstacleGrid), len(obstacleGrid[0])
F = [[0 for x in range(n)] for y in range(m)]
F[0][0] = 1
for row in range(1,m):
if obstacleGrid[row][0] != 1:
F[row][0] = 1
else:
break
for col in range(1,n):
if obstacleGrid[0][col] != 1:
F[0][col] = 1
else:
break
for row in range(1,m):
for col in range(1,n):
if obstacleGrid[row][col] != 1:
F[row][col] = F[row - 1][col] + F[row][col - 1]
else:
F[row][col] = 0
return F[-1][-1]