Type：medium
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
Now consider if some obstacles are added to the grids. How many unique paths would there be?
与上题相比，多了障碍点不可通过。因此只要加判断条件该点不是障碍点即可。
要注意使用longlong型，int不能ac。
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
typedef long long ll;
if(obstacleGrid.size()==0 || obstacleGrid[0].size()==0) return 0;
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector<vector<ll>> dp(m, vector<ll>(n, 0));
for(ll i=0; i<m; i++){
if(obstacleGrid[i][0] == 1) break;
dp[i][0] = 1;
}
for(ll i=0; i<n; i++){
if(obstacleGrid[0][i] == 1) break;
dp[0][i] = 1;
}
for(ll i=1; i<m; i++){
for(ll j=1; j<n; j++){
if(obstacleGrid[i][j] != 1){
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}else dp[i][j] = 0;
}
}
return dp[m-1][n-1];
}
};
