Unique Paths II (求唯一路径）

Follow up for "Unique Paths":

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,

There is one obstacle in the middle of a 3x3 grid as illustrated below.

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

The total number of unique paths is 2.

Note: m and n will be at most 100.

和Unique Path很类似，就是加入了限制，如果obstacle[i][j]=1 那就表示无法到达i,j的位置，加入一些判断修改矩阵就可以了 方法不变。

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
		// IMPORTANT: Please reset any member data you declared, as
		// the same Solution instance will be reused for each test case.
		int m = obstacleGrid.size(), n = obstacleGrid[0].size();
		vector<vector<int> > f(m, vector<int>(n));
		for (int i = 0, flag = 0; i < n; ++i)
		{
			if (obstacleGrid[0][i] == 1) flag = 1;
			if (flag) f[0][i] = 0;
			else f[0][i] = 1;
		}
		for (int i = 0, flag = 0; i < m; ++i)
		{
			if (obstacleGrid[i][0] == 1) flag = 1;
			if (flag) f[i][0] = 0;
			else f[i][0] = 1;
		}
		for(int i = 1; i < m; ++i)
		{
			for(int j = 1; j < n; ++j)
			{
				if ((obstacleGrid[i - 1][j] == 1 && obstacleGrid[i][j - 1]) || obstacleGrid[i][j] == 1)
					f[i][j] = 0;
				else if (obstacleGrid[i - 1][j] == 1)
					f[i][j] = f[i][j- 1];
				else if (obstacleGrid[i][j - 1] == 1)
					f[i][j] = f[i - 1][j];
				else
					f[i][j] = f[i][j-1] + f[i - 1][j];
			}
		}
		return f[m - 1][n - 1];
	}
};