leetcode-63 Unique Paths Ⅱ 题解

题目

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

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

img

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

Note: m and n will be at most 100.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
Input:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

解法

首先分析一下这道题,问的是从左上角走到终点即右下角总共有多少条路径,而且每次只能往右走一步或者往下走一步,如果某个位置的值为1那么就算为障碍,此时是不能走这里的。那么要计算路径的时候,可以分成对每个位置进行处理,这就成为一个DP问题了。对每一个位置来说,它最多就只有两个前置位,也就是它上方与左方的位置,如果该位置处于边界的话那么只有一个前置位。

现在来讨论一下路径数目的计算,对于一个位置(i, j)来说,我们记录了到达它的两个前置位置(i, j -1)(i - 1, j)的路径数,那么到达(i, j)的路径数就应该是两前置位置的路径数之和,这就是路径的计算方法。

实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size(), n = obstacleGrid[0].size();
vector<vector<int>> path(obstacleGrid.size(), vector<int>(obstacleGrid[0].size(), 0)); //记录到达(i, j)的路径数
int dir[2][2] = {{-1, 0}, {0, -1}};
path[0][0] = obstacleGrid[0][0] == 1 ? 0 : 1; //起点的初始路径数
for(int i = 0; i < m; ++i){
for(int j = 0; j < n; ++j){
if(obstacleGrid[i][j] == 1){
path[i][j] = 0;
}
else{
for(int k = 0; k < 2; ++k){
int newi = i + dir[k][0], newj = j + dir[k][1];
if(newi >= 0 && newi < m && newj >= 0 && newj < n){
path[i][j] += path[newi][newj];
}
}
}
}
}
return path[m - 1][n - 1];
}