https://leetcode.com/problems/unique-paths-ii/
Unique Paths II
Total Accepted: 47668 Total Submissions: 169510 Difficulty: Medium
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 3×3 grid as illustrated below.
[ [0,0,0], [0,1,0], [0,0,0] ]
The total number of unique paths is 2.
Note: m and n will be at most 100.
My Code:
class Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid):
"""
:type obstacleGrid: List[List[int]]
:rtype: int
"""
if len(obstacleGrid)==0 or len(obstacleGrid[0])==0:
return 0
ways = [0] * len(obstacleGrid[0])
ways[0] = 1
for j in xrange(0, len(obstacleGrid)):
for i in xrange(0, len(obstacleGrid[0])):
if obstacleGrid[j][i]:
ways[i] = 0
elif i: # only handle cells after the first column
ways[i] = ways[i] + ways[i-1]
return ways[-1]
Idea:
Following my previous post, you only need 1D array to store intermediate number of ways reaching `cell[j][i]`. Other than that, the only difference is that you need to handle obstacle. It is intuitive to do that though: you set `ways[i]=0` if you see an obstacle, i.e., no way can reach a cell without obstacle.