# 不同路径 II
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
示例 1：
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
示例 2：
输入：obstacleGrid = [[0,1],[0,0]]
输出：1
提示：
m == obstacleGrid.lengthn == obstacleGrid[i].length1 <= m, n <= 100obstacleGrid[i][j] 为 0 或 1
以下程序实现了这一功能，请你填补空白处内容：
```cpp
#include
#include
static int uniquePathsWithObstacles(int **obstacleGrid, int obstacleGridRowSize, int obstacleGridColSize)
{
int row, col;
int reset = 0;
for (row = 0; row < obstacleGridRowSize; row++)
{
if (reset)
{
obstacleGrid[row][0] = 1;
}
else
{
if (obstacleGrid[row][0] == 1)
{
reset = 1;
}
}
}
reset = 0;
for (col = 0; col < obstacleGridColSize; col++)
{
if (reset)
{
obstacleGrid[0][col] = 1;
}
else
{
if (obstacleGrid[0][col] == 1)
{
reset = 1;
}
}
}
for (row = 0; row < obstacleGridRowSize; row++)
{
int *line = obstacleGrid[row];
for (col = 0; col < obstacleGridColSize; col++)
{
line[col] ^= 1;
}
}
for (row = 1; row < obstacleGridRowSize; row++)
{
int *last_line = obstacleGrid[row - 1];
int *line = obstacleGrid[row];
for (col = 1; col < obstacleGridColSize; col++)
{
________________________;
}
}
return obstacleGrid[obstacleGridRowSize - 1][obstacleGridColSize - 1];
}
int main(int argc, char **argv)
{
if (argc < 3)
{
fprintf(stderr, "Usage: ./test m n\n");
exit(-1);
}
int i, j, k = 3;
int row_size = atoi(argv[1]);
int col_size = atoi(argv[2]);
int **grids = malloc(row_size * sizeof(int *));
for (i = 0; i < row_size; i++)
{
grids[i] = malloc(col_size * sizeof(int));
int *line = grids[i];
for (j = 0; j < col_size; j++)
{
line[j] = atoi(argv[k++]);
printf("%d ", line[j]);
}
printf("\n");
}
printf("%d\n", uniquePathsWithObstacles(grids, row_size, col_size));
return 0;
}
```
## template
```cpp
#include
#include
static int uniquePathsWithObstacles(int **obstacleGrid, int obstacleGridRowSize, int obstacleGridColSize)
{
int row, col;
int reset = 0;
for (row = 0; row < obstacleGridRowSize; row++)
{
if (reset)
{
obstacleGrid[row][0] = 1;
}
else
{
if (obstacleGrid[row][0] == 1)
{
reset = 1;
}
}
}
reset = 0;
for (col = 0; col < obstacleGridColSize; col++)
{
if (reset)
{
obstacleGrid[0][col] = 1;
}
else
{
if (obstacleGrid[0][col] == 1)
{
reset = 1;
}
}
}
for (row = 0; row < obstacleGridRowSize; row++)
{
int *line = obstacleGrid[row];
for (col = 0; col < obstacleGridColSize; col++)
{
line[col] ^= 1;
}
}
for (row = 1; row < obstacleGridRowSize; row++)
{
int *last_line = obstacleGrid[row - 1];
int *line = obstacleGrid[row];
for (col = 1; col < obstacleGridColSize; col++)
{
if (line[col] != 0)
{
line[col] = line[col - 1] + last_line[col];
}
}
}
return obstacleGrid[obstacleGridRowSize - 1][obstacleGridColSize - 1];
}
int main(int argc, char **argv)
{
if (argc < 3)
{
fprintf(stderr, "Usage: ./test m n\n");
exit(-1);
}
int i, j, k = 3;
int row_size = atoi(argv[1]);
int col_size = atoi(argv[2]);
int **grids = malloc(row_size * sizeof(int *));
for (i = 0; i < row_size; i++)
{
grids[i] = malloc(col_size * sizeof(int));
int *line = grids[i];
for (j = 0; j < col_size; j++)
{
line[j] = atoi(argv[k++]);
printf("%d ", line[j]);
}
printf("\n");
}
printf("%d\n", uniquePathsWithObstacles(grids, row_size, col_size));
return 0;
}
```
## 答案
```cpp
if (line[col] != 0)
{
line[col] = line[col - 1] + last_line[col];
}
```
## 选项
### A
```cpp
if (line[col] == 0)
{
line[col] = line[col - 1] + last_line[col];
}
```
### B
```cpp
if (line[col] != 0)
{
line[col] = line[col + 1] + last_line[col];
}
```
### C
```cpp
if (line[col] == 0)
{
line[col] = line[col + 1] + last_line[col];
}
```