class Solution { public int uniquePathsWithObstacles(int[][] grid) { int m = grid.length; int n = grid[0].length; int dp[][] = new int [m][n]; //if robot is on the 0,0 return 0 if(grid[0][0] == 1) return 0; //traversing first row and coloumn for(int j = 0 ; j < n ; j++){ if(grid[0][j] == 1){ //that is a obstacle exist in this row dp[0][j] = 0; break; } else dp[0][j] = 1; //one way to reach that cell } for(int i = 0 ; i < m ; i++){ if(grid[i][0] == 1){ //that is a obstacle exist in first coloumn dp[i][0] = 0; break; } else dp[i][0] = 1; } for(int i = 0 ; i < m ; i++){ for(int j = 0 ; j < n ; j++){ System.out.print(dp[i][j]); } System.out.println(); } //now traversing rest of the grid for(int i = 1 ; i < m ; i++){ for(int j = 1 ; j < n ; j++){ if(grid[i][j] == 1) dp[i][j] = 0; //no way of reaching if its an obstacle else dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } return dp[m-1][n-1]; } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter