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.

Note: m and n will be at most 100.

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

Difficulty: interview

Starter code:

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        

Solutions:
class Solution:
     def uniquePathsWithObstacles(self, obstacleGrid):
         """
         :type obstacleGrid: List[List[int]]
         :rtype: int
         """
         m = len(obstacleGrid) #row
         n = len(obstacleGrid[0]) #col
         path = [[0 for j in range(n)] for i in range(m)]
         for i in range(m):
             if obstacleGrid[i][0] == 0:
                 path[i][0] = 1
             else:
                 break
         for i in range(n):
             if obstacleGrid[0][i] == 0:
                 path[0][i] = 1
             else:
                 break
         for i in range(1,m):
             for j in range(1,n):
                 if obstacleGrid[i][j] != 1:
                     path[i][j] = path[i-1][j] + path[i][j-1]
                 else:
                     path[i][j] = 0
         return path[m-1][n-1]


class Solution:
     def uniquePathsWithObstacles(self, obstacleGrid):
         """
         :type obstacleGrid: List[List[int]]
         :rtype: int
         """
         
         if not obstacleGrid or not obstacleGrid[0]:
             return 0
 
         m, n = len(obstacleGrid), len(obstacleGrid[0])
 
         # DP:
         #   dp(i, j):   no. of unique paths to obstacleGrid[i][j]
         #   bound:
         #       dp(0, 0) = 0 if obstacleGrid[0][0] == 1 else 1
         #       dp(-1, *) = 0
         #       dp(*, -1) =  0
         #   progress:
         #       dp(i, j) = | 0,             if obstacleGrid[i][j] == 1
         #                  | dp(i-1, j) + dp(i, j-1),           else
 
         dp = [0] * n
         for i in range(m):
             for j in range(n):
                 if obstacleGrid[i][j] == 1:
                     dp[j] = 0
                 else:       
                     if i == 0:
                         if j == 0:
                             dp[j] = 1
                         else:
                             dp[j] = dp[j-1]
                     else:
                         if j > 0:
                             dp[j] = dp[j] + dp[j-1]
                             
         
         return dp[n-1]

class Solution:
     def uniquePathsWithObstacles(self, obstacleGrid):
         """
         :type obstacleGrid: List[List[int]]
         :rtype: int
         """
         if not obstacleGrid:
             return 0
         if obstacleGrid[-1][-1] == 1:
             return 0
         dp = []
         for each in obstacleGrid:
             temp = each[:]
             dp.append(temp)
 
         for i in range(len(dp[0])):
             if obstacleGrid[0][i] == 1:
                 # dp[0][i] = 0
                 break
             else:
                 dp[0][i] = 1
         for j in range(len(dp)):
             if obstacleGrid[j][0] == 1:
                 break
             else:
                 dp[j][0] = 1
         
         # print(dp,obstacleGrid)
         
         for row in range(1, len(obstacleGrid)):
             for col in range(1, len(obstacleGrid[0])):
                 if obstacleGrid[row][col] == 0:
                     if obstacleGrid[row - 1][col] != 1:
                         dp[row][col] += dp[row - 1][col]
                     if obstacleGrid[row][col - 1] != 1:
                         dp[row][col] += dp[row][col - 1]
         print(dp)
         return dp[-1][-1]

class Solution:
     def paths(self,obstacleGrid,n,m,a,b,memo):
         if n>a or m>b:
             return 0
 
         if obstacleGrid[n][m] == 1:
             return 0
 
         if n==a and m==b:
             return 1
 
         if str(n)+" "+str(m) not in memo:
             memo[str(n)+" "+str(m)]=self.paths(obstacleGrid,n+1,m,a,b,memo)+self.paths(obstacleGrid,n,m+1,a,b,memo)
 
         return memo[str(n)+" "+str(m)]
 
         
         
         
         
     def uniquePathsWithObstacles(self, obstacleGrid):
         """
         :type obstacleGrid: List[List[int]]
         :rtype: int
         """
         a = len(obstacleGrid)
         b= len(obstacleGrid[0])
         memo = dict()
         return  self.paths(obstacleGrid,0,0,a-1,b-1,memo)


class Solution:
     def uniquePathsWithObstacles(self, obstacleGrid):
         """
         :type obstacleGrid: List[List[int]]
         :rtype: int
         """
         if len(obstacleGrid)==0 and len(obstacleGrid[0])==0:
             return 1
         if len(obstacleGrid)==0:
             return 0
         
         
         ob=False
         for i in range(len(obstacleGrid)):
             for j in range(len(obstacleGrid[i])):
                 if obstacleGrid[i][j]==1:
                     obstacleGrid[i][j]=None
                     ob=True
                     
         for i in range(len(obstacleGrid)):            
             if obstacleGrid[i][0]==0:
                 obstacleGrid[i][0]=1
             if obstacleGrid[i][0]==None:
                 break
                 
         for i in range(len(obstacleGrid[0])):            
             if obstacleGrid[0][i]==0:
                 obstacleGrid[0][i]=1
             if obstacleGrid[0][i]==None:
                 break
                 
         for i in range(1,len(obstacleGrid)):
             for j in range(1,len(obstacleGrid[i])):
                 if obstacleGrid[i][j]!=None:
                     if obstacleGrid[i-1][j]==None and obstacleGrid[i][j-1]==None:
                         obstacleGrid[i][j]=None
                     elif obstacleGrid[i-1][j]==None and obstacleGrid[i][j-1]!=None:
                         obstacleGrid[i][j]=obstacleGrid[i][j-1]
                     elif obstacleGrid[i-1][j]!=None and obstacleGrid[i][j-1]==None:
                         obstacleGrid[i][j]=obstacleGrid[i-1][j]
                     else:
                         obstacleGrid[i][j]=obstacleGrid[i-1][j]+obstacleGrid[i][j-1]
                 
         if len(obstacleGrid)==1 or len(obstacleGrid[0])==1:
             if ob:
                 return 0
             else:
                 return 1
         
         if obstacleGrid[-1][-1]==None or obstacleGrid[0][0]==None:
             return 0
         
         return obstacleGrid[-1][-1]

class Solution:
     def uniquePathsWithObstacles(self, obstacleGrid):
         """
         :type obstacleGrid: List[List[int]]
         :rtype: int
         1 1 0
         1 1 0
         1 1 0
         """
         if not any(obstacleGrid):
             return 0
 
         n, m = len(obstacleGrid), len(obstacleGrid[0])
         dp = [[1 if i == 0 or j == 0 else 1 for j in range(m)] for i in range(n)]
 
         # Set first column of dp.
         obs = False
         first_col = [i[0] for i in obstacleGrid]
 
         try:
             idx = first_col.index(1)
             for i in range(n):
                 dp[i][0] = 1 if i < idx else 0
         except ValueError:
             pass
 
         # Set first row of dp.
         try:
             first_row = obstacleGrid[0]
             idx = first_row.index(1)
             dp[0] = [1] * idx + [0] * (m - idx)
         except ValueError:
             pass
 
         print(obstacleGrid)
         for i in range(1, n):
             for j in range(1, m):
                 print(i, j)
                 if obstacleGrid[i][j] == 1:
                     dp[i][j] = 0
                 else:
                     dp[i][j] = dp[i-1][j] + dp[i][j-1]
         return dp[n-1][m-1]

class Solution:
     def uniquePathsWithObstacles(self, obstacleGrid):
         """
         :type obstacleGrid: List[List[int]]
         :rtype: int
         """
         m = len(obstacleGrid)
         n = len(obstacleGrid[0])
         P = [[0 for j in range(n+1)] for i in range(m+1)]
         
         P[0][1] = 1
         
         for i in range(1,m+1):
             for j in range(1, n+1):
                 if obstacleGrid[i-1][j-1] != 1:
                     P[i][j] = P[i-1][j] + P[i][j-1]
         return P[m][n]

class Solution:
     def uniquePathsWithObstacles(self, obstacleGrid):
         """
         :type obstacleGrid: List[List[int]]
         :rtype: int
         """
         m = len(obstacleGrid)
         n = len(obstacleGrid[0])
         ResGrid = [[0 for x in range(n+1)] for x in range(m+1)]
         ResGrid[0][1] = 1
 
         for i in range(1, m+1):
             for j in range(1, n+1):
                 if not obstacleGrid[i-1][j-1]:
                     ResGrid[i][j] = ResGrid[i][j-1]+ResGrid[i-1][j]
 
         return ResGrid[m][n]


class Solution:
     def uniquePathsWithObstacles(self, obstacleGrid):
         """
         :type obstacleGrid: List[List[int]]
         :rtype: int
         """
         m = len(obstacleGrid)
         n = len(obstacleGrid[0])
         dp = [0] * n  # 这里先填充了0，这样当i==0时也可以dp[j] += dp[j-1]
         for i in range(m):
             for j in range(n):
                 if obstacleGrid[i][j] == 1:  # 遇到障碍物直接为0
                     dp[j] = 0
                 else:  # 没有遇到障碍物
                     if i == 0 and j == 0:  # 左上角总是为1，也为后面i!=0而j==0的情况做铺垫
                         dp[j] = 1
                     elif j != 0:  # 因为j==0时，应该为dp[j] += 0，等于不变，所以continue
                         dp[j] += dp[j - 1]
         return dp[-1]

class Solution:
     def paths(self,obstacleGrid,n,m,a,b,memo):
         if n>a or m>b:
             return 0
 
         if obstacleGrid[n][m] == 1:
             return 0
 
         if n==a and m==b:
             return 1
 
         if str(n)+" "+str(m) not in memo:
             memo[str(n)+" "+str(m)]=self.paths(obstacleGrid,n+1,m,a,b,memo)+self.paths(obstacleGrid,n,m+1,a,b,memo)
 
         return memo[str(n)+" "+str(m)]
 
         
         
         
         
     def uniquePathsWithObstacles(self, obstacleGrid):
         """
         :type obstacleGrid: List[List[int]]
         :rtype: int
         """
         a = len(obstacleGrid)
         b= len(obstacleGrid[0])
         memo = dict()
         return  self.paths(obstacleGrid,0,0,a-1,b-1,memo)


class Solution:
     def uniquePathsWithObstacles(self, obstacleGrid):
         """
         :type obstacleGrid: List[List[int]]
         :rtype: int
         """
         if not len(obstacleGrid) >0 :
             return 0
             
         m = len(obstacleGrid)
         n = len(obstacleGrid[0])
         arr = [[1 for y in range(n)] for x in range(m)]
         for x in range(m):
             for y in range(n):
                 if x == 0:
                     arr[x][y] = arr[x][y-1]
                 elif y == 0:
                     arr[x][y] = arr[x-1][y]
                 else:
                     arr[x][y] = arr[x-1][y] + arr[x][y-1]
                 if obstacleGrid[x][y] == 1:
                     arr[x][y] = 0
         return arr[-1][-1]

class Solution:
     def uniquePathsWithObstacles(self, obstacleGrid):
         """
         :type obstacleGrid: List[List[int]]
         :rtype: int
         """
         # m * n
         m = len(obstacleGrid)
         n = len(obstacleGrid[0])
         ways = [[0 for i in range(n)] for j in range(m)]
         for i in range(m):
             for j in range(n):
                 if obstacleGrid[i][j] == 1:
                     ways[i][j] = 0
                 elif i == 0 and j == 0:
                     ways[i][j] = 1
                 elif i == 0:
                     ways[i][j] = ways[i][j-1]
                 elif j == 0:
                     ways[i][j] = ways[i-1][j]
                 else:
                     ways[i][j] = ways[i-1][j] + ways[i][j-1]
         return ways[m-1][n-1]
                     


class Solution:
     def uniquePathsWithObstacles(self, obstacleGrid):
         """
         :type obstacleGrid: List[List[int]]
         :rtype: int
         """
         m, n = len(obstacleGrid), len(obstacleGrid[0])
         dp = [[1] * n for _ in range(m)]
         for i in range(m):
             dp[i][0] = 0 if obstacleGrid[i][0] == 1 else dp[i-1][0]
         for j in range(n):
             dp[0][j] = 0 if obstacleGrid[0][j] == 1 else dp[0][j-1]
         
         for i in range(1, m):
             for j in range(1, n):
                 if obstacleGrid[i][j] == 1:
                     dp[i][j] = 0
                 else:
                     dp[i][j] = dp[i-1][j] + dp[i][j-1]
         return dp[m-1][n-1]

class Solution:
     def uniquePathsWithObstacles(self, obstacleGrid):
         """
         :type obstacleGrid: List[List[int]]
         :rtype: int
         """
         m = len(obstacleGrid)
         n = len(obstacleGrid[0])
         mat = [[0] * n for _ in range(m)]
         if not obstacleGrid[0][0]:
             mat[0][0] = 1
         for row in range(m):
             for col in range(n):
                 if col == 0 and row == 0:
                     mat[row][col] = obstacleGrid[row][col] * -1 + 1
                 elif obstacleGrid[row][col] == 1:
                     mat[row][col] == 0
                 else:
                     mat[row][col] = mat[row - 1][col] + mat[row][col - 1]
         return mat[m - 1][n - 1]


class Solution:
     def uniquePathsWithObstacles(self, obstacleGrid):
         """
         :type obstacleGrid: List[List[int]]
         :rtype: int
         """
         m = len(obstacleGrid)
         n = len(obstacleGrid[0])
         
         dp = [[0 for _ in range(n)] for _ in range(m)]
         for i in range(n):
             if obstacleGrid[0][i] == 0:
                 dp[0][i] = 1
             else:
                 break
         for j in range(m):
             if obstacleGrid[j][0] == 0:
                 dp[j][0] = 1
             else:
                 break
         
         if obstacleGrid[m-1][n-1] == 1:
             return 0
         
         print(dp)
 
         for y in range(1, n):
             for x in range(1, m):
                 if obstacleGrid[x][y] == 1:
                     dp[x][y] = 0
                 else: 
                     dp[x][y] = dp[x - 1][y] + dp[x][y - 1]
 
         return dp[m - 1][n - 1]