算法思路

该题和 LeetCode 62. 不同路径 题意一模一样，唯一不同的是路中可能会出现障碍物，即状态不合法的情况，需要做的就是在循环时跳过不合法的格子。

注意： 因为考虑到起点也可能不合法，所以对于起点的初始化应该在循环中判断当前格子是否合法后再对其进行。

C ++代码

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int n = obstacleGrid.size();
        int m = obstacleGrid[0].size();
        vector<vector<long long>> f(n + 1, vector<long long>(m + 1, 0));

        for(int i = 1; i <= n; i++)
           for(int j = 1; j <= m; j++)
           {
               if(obstacleGrid[i - 1][j - 1]) continue;
               if (i == 1 && j == 1) f[i][j] = 1;
               f[i][j] += f[i - 1][j] + f[i][j - 1];
           }

        return f[n][m];
    }
};