题目
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.
分析
这个题是上题的拓展，所以可以采用上题的思路：http://www.jianshu.com/p/c3c54f760907 。区别就是假如出现障碍物，那么这条路就无法通过，因此为0.不过由于计算过程中下一行的数据只需要上一行的数据，因此二维数组可以压缩为一行，进行覆盖计算。最后输出结果即可。
int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridRowSize, int obstacleGridColSize) {
int * ans=(int *)malloc(sizeof(int)*101);
for(int i=0;i<obstacleGridColSize;i++)
{
if(obstacleGrid[0][i]==1)
{
while(i<obstacleGridColSize)
{
ans[i]=0;
i++;
}
}
else
ans[i]=1;
}
for(int i=1;i<obstacleGridRowSize;i++)
{
if(obstacleGrid[i][0]==1)
ans[0]=0;
for(int j=1;j<obstacleGridColSize;j++)
{
if(obstacleGrid[i][j]==1)
ans[j]=0;
else
ans[j]=ans[j-1]+ans[j];
}
//for(int j=0;j<obstacleGridColSize;j++)
// printf("%d ",ans[j]);
//printf("\n");
}
return ans[obstacleGridColSize-1];
}
