题解 | #Shopee的办公室（二）#

本题以动态规划考虑求解 小虾同学只能从两个方向走，即他在每一个坐标的走法是他在该位置前两个方向上坐标走法的和（动态规划分解子问题）。 具体用公式表示为

#状态转移方程
dp[i][j]=dp[i][j-1]+dp[i-1][j]

不能通过boss的位置，所以经过boss位置时，dp数组定义为0 具体代码如下：

x, y,n =map(int,input().split())
ls =[[0 for i in range(y+1)] for j in range(x+1)]

for i in range(n):
    a,b = map(int,input().split())
    ls[a][b]=1
dp = [[0 for i in range(y+1)] for j in range(x+1)]
for i in range(x+1):
    for j in range(y+1):
        if ls[i][j]==1:
            dp[i][j]=0
            continue
        if i==0 or j==0:
            dp[i][j]=1
        else:
            dp[i][j]=dp[i][j-1]+dp[i-1][j]
    
print(dp[x][y])