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.
Example:
There is one obstacle in the middle of a 3x3 grid as illustrated below.
1
2
3
4
5
| [
[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.
Solution
(Unique-Path2.java) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[][] dp = new int[m+1][n+1];
dp[0][1] = 1;
for (int i=1;i<=m;i++){
for (int j=1;j<=n;j++){
if (obstacleGrid[i-1][j-1] == 0)
dp[i][j] = dp[i-1][j]+dp[i][j-1];
}
}
return dp[m][n];
}
}
|
(Unique-Paths2.py) download
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
32
33
34
| class Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid):
"""
:type obstacleGrid: List[List[int]]
:rtype: int
"""
if not obstacleGrid:
return 0
if obstacleGrid[0][0] == 1:
return 0
row = len(obstacleGrid)
col = len(obstacleGrid[0])
dp = [[0]*(col) for i in range(row)]
dp[0][0] = 1
for i in range(1,row):
if obstacleGrid[i][0] == 0:
dp[i][0] = dp[i-1][0]
else:
dp[i][0] = 0
for j in range(1,col):
if obstacleGrid[0][j] == 0:
dp[0][j] = dp[0][j-1]
else:
dp[0][j] = 0
for i in range(1,row):
for j in range(1,col):
if obstacleGrid[i][j] == 1:
dp[i][j] = 0
else:
dp[i][j] = dp[i-1][j]+dp[i][j-1]
return dp[row-1][col-1]
|