63. Unique Paths II

发表于 | 分类于

每日一题 2019 - 04 - 06

题目：

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

解法：

这个题比 leetcode 62 多了一个限制条件就是，地图中可能存在不能通行的障碍物，遇到障碍物需要躲避，那么在这种约束条件下，我们只需要排除异样即可，思路大致如下：

  • 初始化dp地图，dp 第一行 1 位置后不通行，所以 1 后所有可走的情况为 0；dp第一列 1 位置后不通行，所以 1 后所有可走的情况为 0
  • 递推公式依然是 : path[j][i] = path[j - 1][i] + path[j][i - 1];
  • 需要加上限制条件，如果非第一行第一列的其他位置出现 1 ，则该位置的可走的路数的总和为 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
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n;
        if(!m)  return 0;
        else    n = obstacleGrid[0].size();
 
        vector<vector<long long int>> path(m,vector<long long int>(n,0));
        for (int i = 0; i < n; i++)
            if(!obstacleGrid[0][i])
                path[0][i] = 1;
            else    break;
        for (int i = 0; i < m; i++)
            if(!obstacleGrid[i][0])
                path[i][0] = 1;
            else    break;
        for (int i = 1; i < n; i++) 
            for (int j = 1; j < m; j++)
                if(!obstacleGrid[j][i])
                    path[j][i] = path[j - 1][i] + path[j][i - 1];
        return path[m - 1][n - 1];
    }
};
0%
undefined