题解 | Python 过河卒
[NOIP2002 普及组] 过河卒
https://www.nowcoder.com/practice/cc1a9bc523a24716a117b438a1dc5706
n, m, x, y = list(map(int, input().split()))
dp = [[0] * (m + 1) for _ in range(n + 1)]
tag = [[True] * (m + 1) for _ in range(n + 1)]
# 马可以攻击到的点的相对位置
knight_moves = [(0,0), (-2, -1), (-1, -2), (1, -2), (2, -1),
(2, 1), (1, 2), (-1, 2), (-2, 1)]
# 标记马控制的范围
for dx, dy in knight_moves:
nx, ny = x + dx, y + dy
if 0 <= nx <= n and 0 <= ny <= m:
tag[nx][ny] = False
# 初始化起点
dp[0][0] = 1
# 初始化第一行
for j in range(1, m + 1):
if tag[0][j]:
dp[0][j] = dp[0][j - 1]
else:
break
# 初始化第一列
for i in range(1, n + 1):
if tag[i][0]:
dp[i][0] = dp[i - 1][0]
else:
break
# 计算路径
for i in range(1, n + 1):
for j in range(1, m + 1):
if tag[i][j]:
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
print(dp[n][m])
查看30道真题和解析