63. Unique Paths II

Posted on | In | 浏览 次
Words count in article: 500 | Reading time ≈ 2

题目

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?
An obstacle and empty space is marked as 1 and 0respectively 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

题解

  • 题目的意思比较简单，给出一个网格图，以其左上角为起点，右下角为终点，求其左下角到右下角路径的数目。
  • 题目显然是一道动态规划的题目，我们需要做的是理清其中的转移方程，首先题目还有一定的限制，某些格子是不能正常通过的（障碍物），并且只能向下或者向右移动，因此我们可以推出起点位置到当前格子的路径数目为：path[i][j] = path[i-1][j] + path[i][j-1]，对于第一排(i = 0)以及第一列(j=0)则需要额外计算，到达路径数目最多为1，其与前一个格子到达路径数目以及当前格子是否为障碍物有关。

实现代码

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
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {

        /*
        *	path[i][j] = path[i-1][j] + path[i][j-1]
        */

        int path[obstacleGrid.size()][obstacleGrid[0].size()];

        for(int i = 0; i < obstacleGrid.size(); ++i)
            if(!obstacleGrid[i][0])	
                path[i][0] = i >= 1 ? path[i-1][0] : 1;
            else
                path[i][0] = 0;

        for(int j = 0; j < obstacleGrid[0].size(); ++j)
            if(!obstacleGrid[0][j])
                path[0][j] = j >= 1 ? path[0][j-1] : 1;
            else
                path[0][j] = 0;

        for(int i = 1; i < obstacleGrid.size(); ++i)
            for(int j = 1; j < obstacleGrid[0].size(); ++j)
                if(!obstacleGrid[i][j])
                    path[i][j] = path[i-1][j] + path[i][j-1];
                else
                    path[i][j] = 0;

        return path[obstacleGrid.size() - 1][obstacleGrid[0].size() - 1];
    }
};