# 不同路径 II

<p>一个机器人位于一个 <em>m x n </em>网格的左上角 （起始点在下图中标记为“Start” ）。</p>
<p>机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。</p>
<p>现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？</p>
<p><img src="https://img-service.csdnimg.cn/img_convert/dcc604a2757b6fd0e6bdc5155c945ffc.png"
        style="height: 183px; width: 400px;" /></p>
<p>网格中的障碍物和空位置分别用 <code>1</code> 和 <code>0</code> 来表示。</p>
<p> </p>
<p><strong>示例 1：</strong></p><img alt=""
    src="https://img-service.csdnimg.cn/img_convert/d127c16fad8048e19db6f2a2bea73240.jpeg"
    style="width: 242px; height: 242px;" />
<pre><strong>输入：</strong>obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]<strong><br />输出：</strong>2<strong><br />解释：</strong>3x3 网格的正中间有一个障碍物。从左上角到右下角一共有 2 条不同的路径：<br />1. 向右 -> 向右 -> 向下 -> 向下<br />2. 向下 -> 向下 -> 向右 -> 向右</pre>
<p><strong>示例 2：</strong></p><img alt=""
    src="https://img-service.csdnimg.cn/img_convert/d95382b3c9b30e83be3e383421106a67.jpeg"
    style="width: 162px; height: 162px;" />
<pre><strong>输入：</strong>obstacleGrid = [[0,1],[0,0]]<strong><br />输出：</strong>1</pre>
<p> </p>
<p><strong>提示：</strong></p>
<ul>
    <li><code>m == obstacleGrid.length</code></li>
    <li><code>n == obstacleGrid[i].length</code></li>
    <li><code>1 <= m, n <= 100</code></li>
    <li><code>obstacleGrid[i][j]</code> 为 <code>0</code> 或 <code>1</code></li>
</ul>

以下程序实现了这一功能，请你填补空白处内容：

```cpp
#include <stdio.h>
#include <stdlib.h>
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 <stdio.h>
#include <stdlib.h>
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];
}
```