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

Source: leetcode | Difficulty: MEDIUM
Tags: Matrices

Dynamic programming

Data structures

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

Solutions:
class Solution:

	def uniquePathsWithObstacles(self, obstacleGrid):
		m = len(obstacleGrid)
		n = len(obstacleGrid[0])
		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):
		if not obstacleGrid or not obstacleGrid[0]:
			return 0
		(m, n) = (len(obstacleGrid), len(obstacleGrid[0]))
		dp = [0] * n
		for i in range(m):
			for j in range(n):
				if obstacleGrid[i][j] == 1:
					dp[j] = 0
				elif i == 0:
					if j == 0:
						dp[j] = 1
					else:
						dp[j] = dp[j - 1]
				elif j > 0:
					dp[j] = dp[j] + dp[j - 1]
		return dp[n - 1]


class Solution:

	def uniquePathsWithObstacles(self, obstacleGrid):
		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:
				break
			else:
				dp[0][i] = 1
		for j in range(len(dp)):
			if obstacleGrid[j][0] == 1:
				break
			else:
				dp[j][0] = 1
		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):
		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):
		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):
		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)]
		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
		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):
		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):
		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):
		m = len(obstacleGrid)
		n = len(obstacleGrid[0])
		dp = [0] * n
		for i in range(m):
			for j in range(n):
				if obstacleGrid[i][j] == 1:
					dp[j] = 0
				elif i == 0 and j == 0:
					dp[j] = 1
				elif j != 0:
					dp[j] += dp[j - 1]
		return dp[-1]


class Solution:

	def uniquePathsWithObstacles(self, obstacleGrid):
		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):
		(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):
		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):
		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]