NOIP2002过河卒：动态规划求解带马控障碍的右下路径数

这是一个经典的**动态规划（DP）+ 障碍物处理**问题，源自 **NOIP 2002 普及组 第四题** —— “过河卒”。 --- ### 🧩 问题重述（清晰版） - 棋盘是一个二维坐标系，起点 `A = (0, 0)`，终点 `B = (n, m)`。 - 卒只能 **向下（行+1）或向右（列+1）** 移动（即只能走 `(i+1, j)` 或 `(i, j+1)`）。 - 棋盘上有一个马在 `C = (x, y)`，它会控制自身位置以及所有 **“日”字形跳跃一步可达的 8 个点**（即国际象棋中马的走法：`(±1, ±2)` 和 `(±2, ±1)` 共 8 种偏移）。 - 这些被马控制的点（包括马本身）是**不可通行的障碍点**。 - 要求：从 `(0,0)` 到 `(n,m)` 的合法路径总数（只能向右/下，避开所有马的控制点）。 --- ### ✅ 解题思路 #### 1️⃣ 状态定义 设 `dp[i][j]` 表示从 `(0,0)` 走到 `(i,j)` 的路径数。 #### 2️⃣ 状态转移 因为只能从上方或左方来： ```text dp[i][j] = dp[i-1][j] + dp[i][j-1] ``` 但前提是 `(i,j)` **不是障碍点**，且 `i>=0`, `j>=0`。 #### 3️⃣ 边界条件 - `dp[0][0] = 1`（起点，一种方式：不动） - 若 `(0,0)` 是障碍点 → 输出 `0`（但题目保证马不在起点？需判断！样例中马在 (3,3)，起点 (0,0) 安全） #### 4️⃣ 障碍点标记 预处理一个布尔数组 `block[i][j]`，标记哪些点不能走： - 马的位置 `(x, y)` 是障碍； - 所有 8 个马步偏移位置 `(x+dx, y+dy)`，其中 `(dx,dy)` ∈ `{(±1,±2), (±2,±1)}`，也需检查是否在棋盘范围内 `[0..n]×[0..m]`，再标记为 `True`。 > ⚠️ 注意：题目中 `B = (n,m)`，所以棋盘范围是 `0 ≤ i ≤ n`，`0 ≤ j ≤ m`（共 `(n+1) × (m+1)` 个格子） --- ### 🧮 示例分析（样例输入：`6 6 3 3`） - `n=6, m=6` → 终点 `(6,6)` - 马在 `(3,3)` - 马控制点（共 9 个）： - `(3,3)`（自身） - 偏移列表： ``` (3±1, 3±2) → (2,1),(2,5),(4,1),(4,5) (3±2, 3±1) → (1,2),(1,4),(5,2),(5,4) ``` - 全部都在 `[0..6]×[0..6]` 内 → 共 9 个障碍点。 然后 DP 填表即可，结果为 `6`。 --- ### 💻 Python 实现（简洁、安全、带注释） ```python def main(): n, m, x, y = map(int, input().split()) # 初始化障碍数组（大小为 (n+1) x (m+1)） block = [[False] * (m + 1) for _ in range(n + 1)] # 马的8个跳跃方向（dx, dy） dirs = [(-2,-1), (-2,1), (-1,-2), (-1,2), (1,-2), (1,2), (2,-1), (2,1)] # 标记马及其控制点为障碍 if 0 <= x <= n and 0 <= y <= m: block[x][y] = True for dx, dy in dirs: nx, ny = x + dx, y + dy if 0 <= nx <= n and 0 <= ny <= m: block[nx][ny] = True # dp[i][j] 表示到 (i,j) 的路径数 dp = [[0] * (m + 1) for _ in range(n + 1)] # 起点 if not block[0][0]: dp[0][0] = 1 # 填表：逐行逐列（i从0到n，j从0到m） for i in range(n + 1): for j in range(m + 1): if block[i][j]: continue if i > 0: dp[i][j] += dp[i-1][j] if j > 0: dp[i][j] += dp[i][j-1] print(dp[n][m]) if __name__ == "__main__": main() ``` --- ### 📌 关键注意事项（开发建议） | 项目 | 说明 | |------|------| | ✅ **坐标范围** | `0..n` 行，`0..m` 列；不是 `1..n`！注意题目给的是 `B=(n,m)`，含起点 `(0,0)` | | ✅ **障碍预处理** | 必须先标记所有马控点，再开始 DP，否则会误走 | | ✅ **越界检查** | 马跳到 `(x±2,y±1)` 可能越界，务必 `if 0<=nx<=n and 0<=ny<=m` | | ✅ **起点障碍** | 若 `(0,0)` 被马控制（如马在 `(0,0)` 或 `(1,2)` 等），则 `dp[0][0]=0`，整个结果为 0 | | ⚡ **空间优化** | 本题 `n,m ≤ 20`，无需滚动数组；但若扩大规模可优化为一维 `dp[j]` | --- ### 📘 进阶思考（拓展学习） - 若允许向上/向左走？→ 变成带环图，需 DFS+记忆化 或 BFS+状态去重（但本题无环，单向 DAG）。 - 若马会随时间移动？→ 变成「动态障碍」，需加时间维度 `dp[t][i][j]`。 - 若卒可以吃马？→ 控制点仅限马跳到的点，但 `(x,y)` 可通行（除非规则不允许吃）——本题明确说“马所在点和所有跳跃一步可达的点称为控制点”，即**均不可通行**。 --- ######[AI写代码神器 | 1656点数解答 | 2026-03-12 17:56:10]