题目描述

题目链接：63. Unique Paths II

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 space is marked as 1 and 0 respectively in the grid.

例子

例子 1

Input: obstacleGrid = [[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

例子 2

Input: obstacleGrid = [[0,1],[0,0]] Output: 1 Explanation:

例子 3

Input: Output: Explanation:

Follow Up

Note

Constraints

m == obstacleGrid.length n == obstacleGrid[i].length 1 <= m, n <= 100 obstacleGrid[i][j] is 0 or 1.

解题思路

和 [Leetcode]62. Unique Paths(C++) 基本一样的思路，唯一的区别是要考虑障碍物对状态的影响，这一题也很简单，对任意一个位置，如果该位置有障碍物，则在更新完状态之后将其重新设为 0 即可，代码如下：

#include <vector>

class Solution {
public:
    int uniquePathsWithObstacles(std::vector<std::vector<int>>& obstacleGrid) {
        std::vector<std::vector<int>> counts(
            obstacleGrid.size() + 1,
            std::vector<int>(obstacleGrid[0].size() + 1, 0));

        counts[1][1] = 1;
        for (int i = 1; i <= obstacleGrid.size(); ++i) {
            for (int j = 1; j <= obstacleGrid[0].size(); ++j) {
                counts[i][j] = counts[i][j - 1] + counts[i - 1][j];
                if (obstacleGrid[i - 1][j - 1] == 1) {
                    counts[i][j] = 0;
                }
            }
        }

        return counts.back().back();
    }
};

• 时间复杂度: O(mn)
• 空间复杂度: O(mn)

GitHub 代码同步地址： 63.UniquePathsIi.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions