題目

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.

分析

這個(gè)題是上題的拓展，所以可以采用上題的思路：http://www.itdecent.cn/p/c3c54f760907 。區(qū)別就是假如出現(xiàn)障礙物，那么這條路就無法通過，因此為0.不過由于計(jì)算過程中下一行的數(shù)據(jù)只需要上一行的數(shù)據(jù)，因此二維數(shù)組可以壓縮為一行，進(jìn)行覆蓋計(jì)算。最后輸出結(jié)果即可。

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