P1002 [NOIP 2002 普及组] 过河卒 - 解题思路
原题复述
棋盘上 A 点有一个过河卒，需要走到目标 B 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示，A 点 (0, 0)、B 点 (n, m)，同样马的位置坐标是需要给出的。
现在要求你计算出卒从 A 点能够到达 B 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。
输入格式
一行四个正整数，分别表示 $B$ 点坐标和马的坐标。
输出格式
一个整数，表示所有的路径条数。
输入输出样例 #1
输入 #1
6 6 3 3
输出 #1
6
说明/提示
对于 100 % 的数据，1 ≤ n, m ≤ 20，0 ≤ 马的坐标 ≤ 20
【题目来源】
NOIP 2002 普及组第四题
题目描述
棋盘上 A 点有一个过河卒，需要走到目标 B 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。
- A 点 (0, 0)、B 点 (n, m)
- 输入：B 点坐标和马的坐标
- 输出：卒从 A 点到达 B 点的路径条数
- 数据范围：1 ≤ n, m ≤ 20，0 ≤ 马的坐标 ≤ 20
问题简化
想象你在一个网格上，从左上角 (0,0) 走到右下角 (n,m)。你只能往下走或往右走，但有些格子被"马"控制了，不能踩。问：有多少种走法？
第一步：搞清楚哪些格子不能走
马在中国象棋里走"日"字，从马的位置可以跳到8个点。所以马控制的格子 = 马自己的位置 + 8个能跳到的位置。
马能跳到的8个方向（相对马的位置）：
(-2,1), (-1,2), (1,2), (2,1), (2,-1), (1,-2), (-1,-2), (-2,-1)
把这些点全部标记为"禁区"。
第二步：动态规划的核心思想
问自己一个问题：到达格子 (i, j) 有多少种走法？
因为卒只能向下或向右走，所以到达 (i, j) 只有两种可能：
- 从上面 (i-1, j) 走下来
- 从左边 (i, j-1) 走过来
所以：
dp[i][j] = dp[i-1][j] + dp[i][j-1]
意思是：到达当前格子的路径数 = 到达上方格子的路径数 + 到达左边格子的路径数
第三步：处理特殊情况
- 起点
dp[0][0] = 1（只有一种方式：就站在那） - 如果某个格子是禁区，
dp[i][j] = 0（走不了，路径数为0） - 如果起点就是禁区，直接输出0
举个例子
假设没有马，3x3的格子：
1 → 1 → 1
↓ ↓ ↓
1 → 2 → 3
↓ ↓ ↓
1 → 3 → 6
每个格子的数字就是到达它的路径数。右下角是6，说明有6种走法。
如果中间有个禁区，那个格子变成0，后面的格子就会少很多路径。
总结
- 标记马的控制点为禁区
- 从左上角开始，逐格计算路径数
- 禁区路径数为0，其他格子 = 上方 + 左方
- 最后
dp[n][m]就是答案
完整代码
n, m, hx, hy = map(int, input().split())
# 马的8个跳跃方向
horse_moves = [(-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1)]
# 标记马的控制点
blocked = set()
blocked.add((hx, hy))
for dx, dy in horse_moves:
nx, ny = hx + dx, hy + dy
if 0 <= nx <= n and 0 <= ny <= m:
blocked.add((nx, ny))
# DP
dp = [[0] * (m + 1) for _ in range(n + 1)]
dp[0][0] = 0 if (0, 0) in blocked else 1
for i in range(n + 1):
for j in range(m + 1):
if (i, j) in blocked:
dp[i][j] = 0
else:
if i > 0:
dp[i][j] += dp[i - 1][j]
if j > 0:
dp[i][j] += dp[i][j - 1]
print(dp[n][m])