leetCode_63.Unique Paths II 不同路径

题目:

这是“不同路径” 的进阶问题：

现在考虑网格中有障碍物。那样将会有多少条不同的路径从左上角到右下角？

网格中的障碍物和空位置分别用 1 和 0 来表示。

例如，

如下所示在 3×3 的网格中有一个障碍物。

[
  [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改一下代码就好。

下面是熟悉的代码环节@#@：

//
//  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)点处的路径数
    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;
}