Question:
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.
Solution: public class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { int m=obstacleGrid.length; int n=obstacleGrid[0].length; int[][] ans=new int[m][n]; int i=0; int j=0; int flag=0; for(i=0;i<=m-1;i++) { for(j=0;j<=n-1;j++) { if(obstacleGrid[i][j]==1) obstacleGrid[i][j]=-1; } } for(i=0;i<=m-1;i++) { if (obstacleGrid[i][0]==-1||flag==1) { ans[i][0]=0; flag=1; } else ans[i][0]=1; } flag=0; for(j=0;j<=n-1;j++) { if (obstacleGrid[0][j]==-1||flag==1) { ans[0][j]=0; flag=1; } else ans[0][j]=1; } for(i=1;i<=m-1;i++) { for(j=1;j<=n-1;j++) { if(i!=0&&j!=0) { if(obstacleGrid[i][j]==-1) { ans[i][j]=0; } else ans[i][j]=ans[i-1][j]+ans[i][j-1]; } } flag=0; } return ans[i-1][j-1]; } } public class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { int m=obstacleGrid.length,n=obstacleGrid[0].length; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(obstacleGrid[i][j]==0){ if(i==0&&j==0){ obstacleGrid[i][j]=1; }else if(i==0){ obstacleGrid[i][j]=obstacleGrid[i][j-1]; }else if(j==0){ obstacleGrid[i][j]=obstacleGrid[i-1][j]; }else{ obstacleGrid[i][j]=obstacleGrid[i][j-1]+obstacleGrid[i-1][j]; } }else{ obstacleGrid[i][j]=0; } } } return obstacleGrid[m-1][n-1]; } }