題目:

這是“不同路徑” 的進階問題：

現(xiàn)在考慮網(wǎng)格中有障礙物。那樣將會有多少條不同的路徑從左上角到右下角？

網(wǎng)格中的障礙物和空位置分別用 1 和 0 來表示。

例如，

如下所示在 3×3 的網(wǎng)格中有一個障礙物。

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

一共有 2 條不同的路徑從左上角到右下角。

注意: m 和 n 的值均不超過 100。

思路：

這道題大體想法跟Unique Path是一樣的。

只是要單獨考慮下障礙物對整個棋盤的影響。

先看看初始條件會不會受到障礙物的影響。

假設整個棋盤只有一行，那么在第i個位置上設置一個障礙物后，說明位置i到最后一個格子這些路都沒法走了。

如果整個棋盤只有一列，那么第i位置上的障礙物，也會影響從第i位置往后的路。

所以說明，在初始條件時，如果一旦遇到障礙物，障礙物后面所有格子的走法都是0。

再看求解過程，當然按照上一題的分析dp[i][j] = dp[i-1][j] + dp[i][j-1] 的遞推式依然成立（機器人只能向下或者向右走嘛）。但是，一旦碰到了障礙物，那么這時的到這里的走法應該設為0，因為機器人只能向下走或者向右走，所以到這個點就無法通過。

處理完障礙物的特殊問題，依照unique paths改一下代碼就好。

下面是熟悉的代碼環(huán)節(jié)@#@：

//
//  main.cpp
//  UniquePathsII
//
//  Created by 孫艷東 on 2018/4/1.
//  Copyright ? 2018年 com.xidian.edu.cn. All rights reserved.
//

#include <iostream>
#include <vector>

using namespace std;

int uniquePathsWithObstacles(vector<vector<int>> obstacleGrid) {
    int row = obstacleGrid.size(); // 行
    int cols = obstacleGrid[0].size(); // 列
    
    if (obstacleGrid[0][0] == 1 || obstacleGrid[row - 1][cols - 1] == 1) {
        return 0;
    }
    // dp[i][j] 表示到達(i,j)點處的路徑數(shù)
    vector<vector<int>> dp(row, vector<int>(cols,0));
    dp[0][0] = 1;
    // 第一列
    for(int i = 1; i < row; i++) {
        if (obstacleGrid[0][i] == 1) {
            dp[0][i] = 0;
        } else {
            dp[0][i] = dp[0][i - 1];
        }
    }
    // 第一行
    for(int i = 1; i < cols; i++) {
        if (obstacleGrid[i][0] == 1) {
            dp[i][0] = 0;
        } else {
            dp[i][0] = dp[i - 1][0];
        }
    }
    for(int i = 1; i < row; i++) {
        for(int j = 1; j < cols; j ++) {
            if (obstacleGrid[i][j] == 1) {
                dp[i][j] = 0;
            } else {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
    }
    
    
    return dp[row - 1][cols - 1];
}

int main(int argc, const char * argv[]) {
    vector<vector<int> > obstacleGrid = {{0, 0, 0},
                                         {0, 1, 0},
                                         {0, 0, 0}};
    int count = uniquePathsWithObstacles(obstacleGrid);
    cout << count << " \n";
    
    return 0;
}