To solve this problem, we need to count the number of unique paths from the top-left corner to the bottom-right corner of a grid, moving only right or down, while avoiding obstacles. The solution uses dynamic programming (DP) with space optimization to efficiently compute the result.

Approach

1. Dynamic Programming (DP) Setup: We use a 1D DP array where dp[j] represents the number of ways to reach the current row's j-th column. This reduces the space complexity from O(rows*cols) to O(cols).
2. Base Cases:
   • The starting cell (0,0) has 1 path if it's not blocked.
   • For the first row, each cell can only be reached from the left (if not blocked).
   • For the first column, each cell can only be reached from above (if not blocked).
3. DP Transition: For each cell (i,j) (non-first row/column):
   • If the cell is blocked, set dp[j] to 0.
   • Otherwise, dp[j] is the sum of paths from the cell above (previous row's dp[j]) and the cell to the left (current row's dp[j-1]).
4. Modulo Operation: Since the number of paths can be large, we take modulo 10^9+7 to keep the result manageable.

Solution Code

def uniquePathsWithObstacles(grid):
    MOD = 10**9 + 7
    rows = len(grid)
    if rows == 0:
        return 0
    cols = len(grid[0])

    dp = [0] * cols
    # Initialize the starting point
    dp[0] = 1 if grid[0][0] == 0 else 0

    # Fill the first row
    for j in range(1, cols):
        if grid[0][j] == 0:
            dp[j] = dp[j-1] % MOD
        else:
            dp[j] = 0

    # Fill the rest of the rows
    for i in range(1, rows):
        # Update first column of current row
        if grid[i][0] != 0:
            dp[0] = 0
        # Update other columns
        for j in range(1, cols):
            if grid[i][j] == 0:
                dp[j] = (dp[j] + dp[j-1]) % MOD
            else:
                dp[j] = 0

    return dp[-1] % MOD

Explanation

• Space Optimization: Using a 1D array instead of a 2D array saves space, as each row only depends on the previous row and the current row's left values.
• Efficiency: The time complexity is O(rows*cols) since we traverse each cell exactly once. The space complexity is O(cols) due to the 1D DP array.
• Edge Cases: Handles blocked starting/ending cells, empty grids, and grids with all cells blocked.

This approach efficiently computes the number of unique paths while avoiding obstacles, making it suitable for large grids.

Answer: The function returns the number of unique paths modulo 10^9+7. For example, if the input grid is [[0,0,0],[0,1,0],[0,0,0]], the output is 2.

\boxed{2} (for the sample case mentioned) or the result from the function for the given grid. Since the original image is missing, this is a general solution for the common obstacle path problem. If you provide the specific grid, the exact answer can be computed.

作者声明:本文包含人工智能生成内容。