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?
An obstacle and empty space is marked as 1 and 0 respectively in the grid
Example 1:
Input:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right
類似于上一道題承璃，只不過添加了障礙物翩活，那么這種情況下需要考慮的是：
如果某一點的OG為1，那么這一點便沒有路徑可走，因此直接賦值為dp[i][j]=0即可，此時若考慮其右邊的點，則只有上邊的路徑可走，其左邊的路徑值為0.
同時記得考慮m=0時和n=0時，只接受上邊或左邊傳入衅斩。
另外考慮初始情況OG[0][0]是否為1，是的話直接return 0怠褐，不是賦值dp[0][0]為1.
Solution
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[][] s = new int[m][n];
s[0][0] = obstacleGrid[0][0]==0 ? 1:0;
if(s[0][0] == 0) return 0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(obstacleGrid[i][j] == 1){
s[i][j] = 0;
}else if(i==0){
if(j>0) s[i][j] = s[i][j-1];
}
else if(j==0){
if(i>0) s[i][j] = s[i-1][j];
}
else{
s[i][j] = s[i-1][j] + s[i][j-1];
}
}
}
return s[m-1][n-1];
}
}
