《leetCode》：Unique Paths II

本文主要是介绍《leetCode》：Unique Paths II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

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.

思路

思路与上篇博文基本一样。
还是用空间换取时间的思路来做，
只不过这里对障碍物的处理方法为：对该点的到终点的可达路径设为零

实现代码如下：

int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridRowSize, int obstacleGridColSize) {if(obstacleGrid==NULL||obstacleGridRowSize<1||obstacleGridColSize<1){return 0;}int m=obstacleGridRowSize;int n=obstacleGridColSize;//开辟一段空间来保存结果int **result=(int **)malloc(m*sizeof(int *));if(result==NULL){exit(EXIT_FAILURE);}for(int i=0;i<m;i++){result[i]=(int *)malloc(n*sizeof(int));if(result[i]==NULL){exit(EXIT_FAILURE);}memset(result[i],0,n*sizeof(int));//初始化为零 ,很重要}//最后一列为 从下往上故障之前为1，之后为零，表示不可达；   for(int i=m-1;i>=0;i--){if(obstacleGrid[i][n-1]==0){result[i][n-1]=1;}else{break;}}//最后一行为 从右往左故障之前为1，之后为零，表示不可达；   for(int i=n-1;i>=0;i--){if(obstacleGrid[m-1][i]==0){result[m-1][i]=1;}else{break;}}for(int i=m-2;i>=0;i--){for(int j=n-2;j>=0;j--){if(obstacleGrid[i][j]==0){//没有障碍物时，才是右边的点和下边的点的路径之和result[i][j]=result[i+1][j]+result[i][j+1];}//obstacleGrid[i][j]==1时该点的可达路径为零}}return result[0][0];
}

AC结果如下：

这篇关于《leetCode》：Unique Paths II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---