You are given a grid of n * m having 0 and 1 respectively, 0 denotes space, and 1 denotes obstacle. Geek is located at top-left corner (i.e grid[0][0]) and wants to reach the bottom right corner of the grid. A geek can move either down or right at any point of time. return the total number of ways in which Geek can reach bottom right corner. answer may be large take the modulo by 1e9+7.
Example:
Input:
n = 3, m = 3
grid= [[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
Example 2:
Input:
n = 2, m = 2
grid = [[0,1],[0,0]]
Output:
1
Your Task:
You don't have to read input or print anything. Your task is to complete the function totalWays() which takes the integer n and m and m * n grid.
Constraint:
1 <= m,n <= 100
grid[i][j] is 0 or 1.
Expected Time Complexity: O(m * n)
Expected Space Complexity: O(n)

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: #User function Template for python3



class Solution:

    def totalWays(self, n, m, grid):

        # Code here

Solutions:
M = 1000000007

class Solution:

	def totalWays(self, n, m, grid):
		dp = [[-1 for j in range(m)] for i in range(n)]
		prev = [0] * m
		for i in range(n):
			cur = [0] * m
			for j in range(m):
				if grid[i][j] == 1:
					cur[j] = 0
				elif i == 0 and j == 0:
					cur[j] = 1
				else:
					up = left = 0
					if i > 0:
						up = prev[j]
					if j > 0:
						left = cur[j - 1]
					cur[j] = (up + left) % M
			prev = cur
		return prev[m - 1]


M = 1000000007

class Solution:

	def totalWays(self, n, m, grid):
		dp = [[-1 for j in range(m)] for i in range(n)]
		return self.ways(n - 1, m - 1, grid, dp)

	def ways(self, a, b, grid, dp):
		if a >= 0 and b >= 0 and (grid[a][b] == 1):
			return 0
		if a == 0 and b == 0:
			return 1
		if a < 0 or b < 0:
			return 0
		if dp[a][b] != -1:
			return dp[a][b]
		up = self.ways(a - 1, b, grid, dp)
		left = self.ways(a, b - 1, grid, dp)
		dp[a][b] = up + left
		return dp[a][b] % M


class Solution:

	def totalWays(self, n, m, obstacleGrid):
		if obstacleGrid[0][0] == 1 or obstacleGrid[-1][-1] == 1:
			return 0
		copy = [[0] * len(obstacleGrid[0]) for _ in range(len(obstacleGrid))]
		copy[0][0] = 1
		mod = 10 ** 9 + 7
		for i in range(len(copy)):
			for j in range(len(copy[0])):
				if j > 0 and i > 0:
					if obstacleGrid[i - 1][j] != 1 and obstacleGrid[i][j - 1] != 1:
						copy[i][j] = copy[i - 1][j] + copy[i][j - 1]
					elif obstacleGrid[i - 1][j] == 1 and obstacleGrid[i][j - 1] != 1:
						copy[i][j] = copy[i][j - 1]
					elif obstacleGrid[i - 1][j] != 1 and obstacleGrid[i][j - 1] == 1:
						copy[i][j] = copy[i - 1][j]
				elif j > 0 and i == 0 and (obstacleGrid[i][j - 1] != 1):
					copy[i][j] = copy[i][j - 1]
				elif j == 0 and i > 0 and (obstacleGrid[i - 1][j] != 1):
					copy[i][j] = copy[i - 1][j]
		return copy[-1][-1] % mod


class Solution:

	def totalWays(self, n, m, grid):
		MOD = 10 ** 9 + 7
		dp = [[0 for _ in range(m)] for _ in range(n)]
		dp[0][0] = 1
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1:
					dp[i][j] = 0
				elif i == 0 and j == 0:
					continue
				else:
					dp[i][j] = ((dp[i - 1][j] if 0 <= i < n else 0) + (dp[i][j - 1] if 0 <= j < m else 0)) % MOD
		return dp[n - 1][m - 1]


class Solution:

	def totalWays(self, a, b, grid):
		if grid[0][0] == 1:
			return 0
		grid[0][0] = 1
		for i in range(a):
			for j in range(b):
				if i == 0 and j == 0:
					continue
				if grid[i][j] == 1:
					grid[i][j] = 0
					continue
				left = up = 0
				if i - 1 >= 0:
					up = grid[i - 1][j]
				if j - 1 >= 0:
					left = grid[i][j - 1]
				grid[i][j] += left + up
				grid[i][j] %= 1000000007
		return grid[a - 1][b - 1]


mod = 10 ** 9 + 7

class Solution:

	def totalWays(self, n, m, grid):
		if n == 1 and m == 1 and (grid[0][0] == 1):
			return 0
		dp = [[-1 for i in range(m + 1)] for j in range(n + 1)]

		def dfs(i, j):
			if i == n - 1 and j == m - 1:
				return 1
			if i < 0 or i >= n or j < 0 or (j >= m):
				return 0
			if grid[i][j] == 1:
				dp[i][j] = 0
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			dp[i][j] = (dfs(i + 1, j) + dfs(i, j + 1)) % mod
			return dp[i][j] % mod
		return dfs(0, 0)


class Solution:

	def totalWays(self, n, m, grid):
		M = int(1000000000.0 + 7)
		dp = [[0 for _ in range(m)] for _ in range(n)]
		dp[0][0] = 1 if grid[0][0] == 0 else 0
		for j in range(1, m):
			if grid[0][j] == 0:
				dp[0][j] = dp[0][j - 1]
			else:
				dp[0][j] = 0
		for i in range(1, n):
			if grid[i][0] == 0:
				dp[i][0] = dp[i - 1][0]
			else:
				dp[i][0] = 0
		for i in range(1, n):
			for j in range(1, m):
				if grid[i][j] == 0:
					dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % M
				else:
					dp[i][j] = 0
		return dp[n - 1][m - 1]


class Solution:

	def totalWays(self, n, m, grid):
		mod = 10 ** 9 + 7
		if grid[0][0] == 1:
			return 0
		if grid[n - 1][m - 1] == 1:
			return 0
		else:
			dp = [[-1 for j in range(m)] for i in range(n)]
			dp[0][0] = 1
			for j in range(1, m):
				if grid[0][j] == 1:
					dp[0][j] = 0
				else:
					dp[0][j] = dp[0][j - 1]
			for i in range(1, n):
				if grid[i][0] == 1:
					dp[i][0] = 0
				else:
					dp[i][0] = dp[i - 1][0]
			for i in range(1, n):
				for j in range(1, m):
					if grid[i][j] == 1:
						dp[i][j] = 0
					else:
						dp[i][j] = (dp[i - 1][j] % mod + dp[i][j - 1] % mod) % mod
			return dp[n - 1][m - 1]


class Solution:

	def totalWays(self, m, n, obstacleGrid):
		if obstacleGrid[m - 1][n - 1] == 1:
			return 0
		for i in range(1, m):
			obstacleGrid[i][0] = max(obstacleGrid[i - 1][0], obstacleGrid[i][0])
		for j in range(1, n):
			obstacleGrid[0][j] = max(obstacleGrid[0][j], obstacleGrid[0][j - 1])
		for i in range(m):
			for j in range(n):
				if obstacleGrid[i][j] == 0:
					obstacleGrid[i][j] = 1
				elif obstacleGrid[i][j] == 1:
					obstacleGrid[i][j] = 0
		for i in range(1, m):
			for j in range(1, n):
				if obstacleGrid[i][j] == 0:
					continue
				obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]
		return obstacleGrid[m - 1][n - 1] % 1000000007


class Solution:

	def totalWays(self, m, n, obstacleGrid):
		dp = [[0] * n for _ in range(m)]
		dp[-1][-1] = 1 if obstacleGrid[-1][-1] == 0 else 0
		if dp[-1][-1] == 0:
			return 0
		mod = 10 ** 9 + 7
		for i in range(m - 1, -1, -1):
			for j in range(n - 1, -1, -1):
				if i == m - 1 and j == n - 1:
					continue
				if obstacleGrid[i][j] == 1:
					continue
				if i == m - 1:
					dp[i][j] = dp[i][j + 1] if obstacleGrid[i][j + 1] == 0 else 0
					continue
				if j == n - 1:
					dp[i][j] = dp[i + 1][j] if obstacleGrid[i + 1][j] == 0 else 0
					continue
				dp[i][j] += dp[i + 1][j] if obstacleGrid[i + 1][j] == 0 else 0
				dp[i][j] += dp[i][j + 1] if obstacleGrid[i][j + 1] == 0 else 0
				dp[i][j] %= mod
		return dp[0][0]


class Solution:

	def totalWays(self, n, m, grid):
		dp = [[-1 for _ in range(m)] for _ in range(n)]
		mod = 1000000000.0 + 7

		def helper(x, y):
			if x >= 0 and y >= 0 and (grid[x][y] == 1):
				return 0
			if x == 0 and y == 0:
				return 1
			if x < 0 or y < 0:
				return 0
			if dp[x][y] != -1:
				return dp[x][y]
			up = helper(x - 1, y)
			left = helper(x, y - 1)
			dp[x][y] = (up + left) % mod
			return dp[x][y]
		return int(helper(n - 1, m - 1))


from math import inf

class Solution:

	def totalWays(self, n, m, grid):
		lim = 10 ** 9 + 7
		tabarray = [[0 for i in range(m)] for j in range(n)]
		tabarray[0][0] = 1
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1:
					tabarray[i][j] = 0
					continue
				if j > 0:
					tabarray[i][j] = (tabarray[i][j] + tabarray[i][j - 1]) % lim
				if i > 0:
					tabarray[i][j] = (tabarray[i][j] + tabarray[i - 1][j]) % lim
		return tabarray[n - 1][m - 1]