左上角到右下角路径（有障碍）

---

题目描述

如果在图中加入了一些障碍，有多少不同的路径？

分别用0和1代表空区域和障碍

例如

下图表示有一个障碍在3*3的图中央。

[↵  [0,0,0],↵  [0,1,0],↵  [0,0,0]↵]

有2条不同的路径

备注：m和n不超过100.

解题思路

这道题是上道机器人运动轨迹条数的一个升级版。它提前给出了一个矩阵，标记出机器人不能经过的点。机器人由左上角到右下角的路径条数。

首先想到的就是构造一个相同大小并初始化为全为1的矩阵。然后在遍历矩阵时，遇到标记为1的障碍位置时，则到此点的路径为0。其他位置如上题一样dp[i][j]=dp[i-1][j]+dp[i][j-1]计算，结果发现只能通过一部分测试。

根据参考别人的代码和运行失败的例子发现，错误发生在第一列和第一行。当一行中只要出现障碍1，到知道位置的路径条数均为0;在一列中也是同样的道理。因此要单独对第一列和第一行进行初始化操作。

但是要是采用构造一个同列数相等的一维数组，就不需要考虑了。

代码

class Solution
{
public:
    int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid)
    {
        int row = obstacleGrid.size();
        int col = obstacleGrid[0].size();
        
        vector<vector<int> > dp(row, vector<int>(col, 0));
        for (int i = 0; i < row; i++)
        {
            if (obstacleGrid[i][0])
                break;
            dp[i][0] = 1;
        }
        for (int j = 0; j < col; j++)
        {
            if (obstacleGrid[0][j])
                break;
            dp[0][j] = 1;
        }
        
        // 因为已经对第一行和第一列进行了初始化，所以直接跳过第一行和第一列
        for (int i = 1; i < row; i++)
        {
            for (int j = 1; j < col; j++)
            {
                if (obstacleGrid[i][j])
                    dp[i][j] = 0;
                else
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[row - 1][col - 1];
    }
};

使用一维数组：

class Solution
{
public:
    int uniquePathsWithObstacles (vector<vector<int> >& obstacleGrid)
    {
        int row = obstacleGrid.size();
        int col = obstacleGrid[0].size();
        
        vector<int> dp(col, 0);
        dp[0] = 1;
        
        for (int i = 0; i < row; i++)
            for (int j = 0; j < col; j++)
            {
                if (obstacleGrid[i][j])
                    dp[j] = 0;
                else
                    dp[j] += dp[j - 1];
            }
    	return dp[col - 1];
    
    }
};

参考链接：

https://www.nowcoder.com/questionTerminal/3cdf08dd4e974260921b712f0a5c8752?f=discussion