题解 | [NOIP2002 普及组] 过河卒 Python3

import sys

# 23:28

# 动态规划 dp[i][j]为从 （0，0）到 （i，j)的条数
# 可以从上面来，也可以从左边来
# dp[i+1][j] = dp[i][j] + dp[i+1][j-1]，且 (i,j), (i+1,j-1)不为马能吃掉的点，否则不加该点

n, m, x, y = list(map(int, input().split()))

dp = [[0]*(m+1) for _ in range(n+1)]

dp[0][0] = 1

# 初始化dp[0][i]

for i in range(1,m+1):
    # 第一行，只能从右边走
    if (abs(0-x) + abs(i-y) == 3 and x!=0 and y!=i) or (x==0 and y==i):
        # 遇到马范围，不能走
        dp[0][i] = 0
    else:
        dp[0][i] = dp[0][i-1]

for i in range(1,n+1):
    # 第一列，只能从下边走
    if (abs(i-x) + abs(0-y) == 3 and x!=i and y!=0) or (i==x and y==0):
        # 遇到马范围，不能走
        dp[i][0] = 0
    else:
        dp[i][0] = dp[i-1][0]

for i in range(1,n+1):
    for j in range(1,m+1):
        # 如果（i，j）在马能吃到的范围内，或者为马。直接什么都不处理
        if (abs(i-x) + abs(j-y) == 3 and x!=i and y!=j) or (x==i and y==j):
            continue           
        dp[i][j] = dp[i-1][j] + dp[i][j-1]

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