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)

见题面

见题面