还是老规矩，先看看29. Unique Paths，那道题我开始尽量使用示意图去描述算法意图。自我感觉还算清楚。
这道题增加了一个限制条件，路径上出现两种状态：此路可通（0），此路不通（1）。且参数也变成了一个二维的 vector.
但这并不妨碍我们继续使用动态规划算法，依旧是弄一个数组（记录到某个位置所有可能的路径数），先读取二维矩阵的第一行（如果有的话）。假设第一行如下：
0 0 0 1 0 1 0 0
^
// 出现1，表示横着的这条路不通，那么其后续的全部位置（包括自身），都应该是0。变成下面这个样子：
1 1 1 0 0 0 0 0
// 如何实现上述的转变？
vector<int> vec(obstacleGrid.front().cbegin(), obstacleGrid.front().cend()); // 读取第一行
auto flag = std::find(vec.begin(), vec.end(), 1); // 找到第一个出现的1所在位置，若没有 flag == vec.end();
std::fill(vec.begin(), flag, 1); // 将前面的节点置为1
std::fill(flag, vec.end(), 0); // 将后面的节点置为0后面的过程与 29 题几乎一致了。除了第一列外，基本遵循以下逻辑：
#include <vector>
#include <algorithm>
#include <iostream>
#include <iterator>
using std::vector; using std::prev;
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
if (obstacleGrid.empty()) return 0;
vector<int> vec(obstacleGrid.front().cbegin(), obstacleGrid.front().cend());
auto flag = std::find(vec.begin(), vec.end(), 1);
std::fill(vec.begin(), flag, 1);
std::fill(flag, vec.end(), 0);
for (auto line = std::next(obstacleGrid.cbegin()); line != obstacleGrid.cend(); ++line) {
auto iter = vec.begin();
for (auto i : *line) {
if (i) *iter = 0;
else if (iter != vec.begin()) *iter += *prev(iter);
++iter;
}
}
return vec.back();
}
};