题目
"不同的路径" 的跟进问题：
现在考虑网格中有障碍物，那样将会有多少条不同的路径？
网格中的障碍和空位置分别用 1 和 0 来表示。
** 注意事项
m 和 n 均不超过100 **
样例
如下所示在3x3的网格中有一个障碍物：
diffRoute2.PNG
一共有2条不同的路径从左上角到右下角。
分析
依然和前述的不同路径问题一样，就是增加了障碍点，遇到障碍点我们就跳过即可。
代码
public class Solution {
/**
* @param obstacleGrid: A list of lists of integers
* @return: An integer
*/
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
// write your code here
int[][] dp = new int[100][100];
int r=obstacleGrid.length;
int c=obstacleGrid[0].length;
for(int i=0;i<r;++i){ //第一列
if(0==obstacleGrid[i][0]) //因为只能向下或者向右走，所以从起点来到该点方法有一种
dp[i][0]=1;
else
break; //阻塞了，接下来不用考虑下面的点，肯定走不到
}
for(int i=0;i<c;++i){ //第一行 同理
if(0==obstacleGrid[0][i])
dp[0][i]=1;
else
break;
}
for(int i=1;i<r;++i)
for(int j=1;j<c;++j){
if(0==obstacleGrid[i][j])
dp[i][j]=dp[i-1][j]+dp[i][j-1]; //从起点走到该点有几种途径等于
//从起点到该点上面的点和该点左
//边的点途径之和
else
dp[i][j]=0;
}
return dp[r-1][c-1];
}
}
