To solve the grid path problem (moving only right or down while avoiding obstacles), we use dynamic programming (DP) to count valid paths from the top-left to the bottom-right corner of the grid.

Approach

1. Dynamic Programming Table: dp[i][j] represents the number of ways to reach cell (i,j) from the top-left corner (0,0).
2. Base Cases:
   • dp[0][0] = 1 if it's not an obstacle (starting point).
   • First row: Only right moves are allowed, so dp[0][j] = dp[0][j-1] if no obstacle at (0,j).
   • First column: Only down moves are allowed, so dp[i][0] = dp[i-1][0] if no obstacle at (i,0).
3. Transition: For any cell (i,j), if it's not an obstacle, dp[i][j] = dp[i-1][j] + dp[i][j-1] (sum of ways from above and left).
4. Modulo: Use modulo 1e9+7 to handle large numbers (common in programming problems).

Solution Code

MOD = 10**9 + 7

# Example input handling (adjust based on actual problem input)
# Assume input: n m, then k obstacles, then k lines of (x,y) (1-based)
n, m = map(int, input().split())
k = int(input())
obstacles = set()
for _ in range(k):
    x, y = map(int, input().split())
    obstacles.add((x-1, y-1))  # convert to 0-based

# Initialize DP table
dp = [[0]*m for _ in range(n)]
if (0,0) not in obstacles:
    dp[0][0] = 1

# Fill first row
for j in range(1, m):
    if (0, j) not in obstacles:
        dp[0][j] = dp[0][j-1]
    else:
        dp[0][j] = 0

# Fill first column
for i in range(1, n):
    if (i, 0) not in obstacles:
        dp[i][0] = dp[i-1][0]
    else:
        dp[i][0] = 0

# Fill rest of the table
for i in range(1, n):
    for j in range(1, m):
        if (i,j) in obstacles:
            dp[i][j] = 0
        else:
            dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MOD

print(dp[n-1][m-1])

Explanation

• Obstacle Handling: Cells with obstacles are marked as 0 (no valid paths to reach them).
• Efficiency: The DP table is filled in O(n*m) time, which is optimal for grid problems of reasonable size.

To get the exact answer, input the grid size and obstacle coordinates into this code. For example, if the grid is 3x3 with an obstacle at (1,1) (0-based), the output will be 2.

Let me know if you need help with specific input values!

（免责声明：本文为本网站出于传播商业信息之目的进行转载发布，不代表本网站的观点及立场。本文所涉文、图、音视频等资料的一切权利和法律责任归材料提供方所有和承担。本网站对此资讯文字、图片等所有信息的真实性不作任何保证或承诺，亦不构成任何购买、投资等建议，据此操作者风险自担。） 本文为转载内容，授权事宜请联系原著作权人，如有侵权，请联系本网进行删除。