package com.fishercoder.solutions;

/**
 * 63. Unique Paths II

 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.

Note: m and n will be at most 100.*/
public class _63 {
  public static class Solution1 {
    /**
     * Idea: grid[i][j] has to be set to zero if obstacleGrid[i][j] == 1, otherwise, we can get
     * dp[i][j] from its top and left dp.
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
      if (obstacleGrid == null || obstacleGrid.length == 0) {
        return 0;
      }

      int height = obstacleGrid.length;
      int width = obstacleGrid[0].length;
      int[][] dp = new int[height][width];
      dp[0][0] = obstacleGrid[0][0] == 1 ? 0 : 1;
      for (int i = 1; i < height; i++) {
        dp[i][0] = obstacleGrid[i][0] == 1 ? 0 : dp[i - 1][0];
      }
      for (int j = 1; j < width; j++) {
        dp[0][j] = obstacleGrid[0][j] == 1 ? 0 : dp[0][j - 1];
      }

      for (int i = 1; i < height; i++) {
        for (int j = 1; j < width; j++) {
          if (obstacleGrid[i][j] == 1) {
            dp[i][j] = 0;
          } else {
            int paths = 0;
            if (obstacleGrid[i - 1][j] == 0) {
              paths += dp[i - 1][j];
            }
            if (obstacleGrid[i][j - 1] == 0) {
              paths += dp[i][j - 1];
            }
            dp[i][j] = paths;
          }
        }
      }
      return dp[height - 1][width - 1];
    }
  }
}

@@ -33,437 +33,8 @@
 s;%0A%0A
-/**%0A * 63. Unique Paths II%0A%0A Follow up for %22Unique Paths%22:%0A%0ANow consider if some obstacles are added to the grids. How many unique paths would there be?%0A%0AAn obstacle and empty space is marked as 1 and 0 respectively in the grid.%0A%0AFor example,%0AThere is one obstacle in the middle of a 3x3 grid as illustrated below.%0A%0A%5B%0A  %5B0,0,0%5D,%0A  %5B0,1,0%5D,%0A  %5B0,0,0%5D%0A%5D%0AThe total number of unique paths is 2.%0A%0ANote: m and n will be at most 100.*/%0A
 publ
@@ -48,16 +48,18 @@
 s _63 %7B%0A
+  
   public
@@ -84,16 +84,20 @@
 tion1 %7B%0A
+    
     /**%0A
@@ -101,16 +101,20 @@
 **%0A     
+   
+ 
 * Idea: 
@@ -201,16 +201,20 @@
 et%0A     
+    
 * dp%5Bi%5D%5B
@@ -251,15 +251,23 @@
     
+    
 */%0A    
+  
+  
 publ
@@ -324,24 +324,30 @@
 id) %7B%0A      
+    
+  
 if (obstacle
@@ -394,24 +394,32 @@
 ) %7B%0A        
+    
+    
 return 0;%0A  
@@ -412,24 +412,30 @@
   return 0;%0A
+      
       %7D%0A%0A   
@@ -433,24 +433,30 @@
    %7D%0A%0A      
+ 
+     
 int height =
@@ -469,32 +469,38 @@
 cleGrid.length;%0A
+      
       int width 
@@ -521,24 +521,30 @@
 %5B0%5D.length;%0A
+      
       int%5B%5D%5B
@@ -576,24 +576,30 @@
 dth%5D;%0A      
+     
+ 
 dp%5B0%5D%5B0%5D = o
@@ -630,16 +630,22 @@
  0 : 1;%0A
+      
       fo
@@ -681,24 +681,32 @@
 ) %7B%0A        
+    
+    
 dp%5Bi%5D%5B0%5D = o
@@ -748,16 +748,22 @@
  1%5D%5B0%5D;%0A
+      
       %7D%0A
@@ -764,24 +764,30 @@
     %7D%0A      
+ 
+     
 for (int j =
@@ -800,32 +800,40 @@
 %3C width; j++) %7B%0A
+        
         dp%5B0%5D%5Bj%5D
@@ -885,25 +885,37 @@
 ;%0A      
-%7D%0A%0A
+      %7D%0A%0A   
       
+   
 for (int
@@ -941,32 +941,40 @@
  i++) %7B%0A        
+   
+     
 for (int j = 1; 
@@ -993,32 +993,42 @@
 ++) %7B%0A          
+ 
+         
 if (obstacleGrid
@@ -1046,32 +1046,44 @@
 ) %7B%0A            
+  
+          
 dp%5Bi%5D%5Bj%5D = 0;%0A  
@@ -1090,16 +1090,26 @@
         
+ 
+         
 %7D else %7B
@@ -1117,24 +1117,36 @@
             
+  
+          
 int paths = 
@@ -1144,24 +1144,36 @@
  paths = 0;%0A
+            
             
@@ -1213,32 +1213,46 @@
 %7B%0A              
+ 
+             
 paths += dp%5Bi - 
@@ -1262,34 +1262,58 @@
 j%5D;%0A            
+         
-%7D%0A
+   %7D%0A            
             if (
@@ -1349,32 +1349,46 @@
 %7B%0A              
+        
+      
 paths += dp%5Bi%5D%5Bj
@@ -1398,34 +1398,50 @@
 1%5D;%0A            
-%7D%0A
+            %7D%0A    
             dp%5Bi
@@ -1428,32 +1428,40 @@
                 
+        
 dp%5Bi%5D%5Bj%5D = paths
@@ -1476,28 +1476,58 @@
     
-%7D%0A        %7D%0A      %7D%0A
+          %7D%0A                %7D%0A            %7D%0A      
     
@@ -1566,16 +1566,22 @@
 1%5D;%0A    
-%7D%0A
+    %7D%0A  
   %7D%0A%7D%0A

refactor 63