题目

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];
}