题目要求
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 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.
Note: m and n will be at most 100.
|
这是Unique Path题目系列。关于Unique Path I请参考我的这篇博客。相比于I，这里添加的需求是说，某些节点上存在路障。存在路障的节点会在数组中被标记为1。请问从起点到终点有多少条独立路径。
思路和代码
在Unique Path I的思路基础上，我们可以知道，如果某个节点上存在路障，那么任何从该节点前往终点的路径都将不存在。也就是说，该节点的路径数为0。在此基础上，我们可以知道，如果该节点为路障，则该节点路径数为0，否则该节点的路径数等于左侧节点路径数和上方节点路径数的和。代码如下：
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
| public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int row = obstacleGrid.length;
if(row==0){
return 0;
}
int column = obstacleGrid[0].length;
int path = obstacleGrid[0][0] == 1 ? 0 : 1;
for(int i = 1 ; i<row ; i++){
if(obstacleGrid[i][0] == 1){
path = 0;
}
obstacleGrid[i][0] = path;
}
path = 1;
for(int i = 0 ; i<column ; i++){
if(obstacleGrid[0][i] == 1){
path = 0;
}
obstacleGrid[0][i] = path;
}
for(int i = 1 ; i<row ; i++){
for(int j = 1 ; j<column ; j++){
if(obstacleGrid[i][j] == 1){
obstacleGrid[i][j] = 0;
}else{
obstacleGrid[i][j] = obstacleGrid[i][j-1] + obstacleGrid[i-1][j];
}
}
}
return obstacleGrid[row-1][column-1];
}
|