题意
给出一个
n∗m
的地图，地图中会存在障碍，求从左上角到右下角的方案数，只能向右走或者向下走
思路
和上一题62. Unique Paths差不多，只是多了一些障碍，只需要判断一下就可以了，需要注意对于边界的处理如果前一步不能到达，那么当前也是不可能到达的.
代码
class Solution {
public:
int uniquePathsWithObstacles(
vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
if(m ==
0)
return 0;
int n = obstacleGrid[
0].size();
vector<vector<int> >dp(m,
vector<int>(n));
for(
int i =
0; i < m; i++){
dp[i][
0] = (obstacleGrid[i][
0] ==
0);
if(i && dp[i-
1][
0] ==
0) dp[i][
0] =
0;
}
for(
int i =
0; i < n; i++){
dp[
0][i] = (obstacleGrid[
0][i] ==
0);
if(i && dp[
0][i -
1] ==
0) dp[
0][i] =
0;
}
for(
int i =
1; i < m; i++){
for(
int j =
1; j < n; j++){
if(obstacleGrid[i][j] ==
1){
dp[i][j] =
0;
}
else{
dp[i][j] = dp[i -
1][j] + dp[i][j -
1];
}
}
}
return dp[m -
1][n -
1];
}
};
