題目:
這是“不同路徑” 的進階問題：
現(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;
}
