P1002 [NOIP 2002 普及组] 过河卒
题目描述
棋盘上 \(A\) 点有一个过河卒，需要走到目标 \(B\) 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 \(C\) 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示，\(A\) 点 \((0, 0)\)、\(B\) 点 \((n, m)\)，同样马的位置坐标是需要给出的。
现在要求你计算出卒从 \(A\) 点能够到达 \(B\) 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。
输入格式
一行四个正整数，分别表示 \(B\) 点坐标和马的坐标。
输出格式
一个整数，表示所有的路径条数。
输入输出样例 #1
输入 #1
输出 #1
说明/提示
对于 \(100 \%\) 的数据，\(1 \le n, m \le 20\)，\(0 \le\) 马的坐标 \(\le 20\)。
保证起点不是马的控制点。
【题目来源】
NOIP 2002 普及组第四题
Tip
📌 题目分析
👉 本质：
从 (0,0) 走到 (n,m)，每次只能：
但有一些格子被马控制，不能走。
👉 要求：
👉 类型： 动态规划（网格路径计数）
🧠 解题思路
1️⃣ 核心建模
设：
表示：
2️⃣ 状态转移（核心）
因为只能从：
- 上面
(i-1,j)向下走来 - 左边
(i,j-1)向右走来
所以：
3️⃣ 障碍处理（马控制点）
这些格子不能走：
- 马所在位置
- 马能跳到的位置（8个方向）
马走法：
把这些位置标记为：
4️⃣ 初始化
起点：
前提是起点没被封锁（题目保证）
5️⃣ 为什么用 long long
路径数量可能很大：
所以必须：
6️⃣ 时间复杂度
网格大小最大：
复杂度：
非常快 ✅
💻 C++代码
#include <bits/stdc++.h>
using namespace std;
long long dp[25][25];
bool ban[25][25];
int dx[9] = {0, 1, 1, -1, -1, 2, 2, -2, -2};
int dy[9] = {0, 2, -2, 2, -2, 1, -1, 1, -1};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, x, y;
cin >> n >> m >> x >> y;
// 标记马及控制点
for (int k = 0; k < 9; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx >= 0 && nx <= n && ny >= 0 && ny <= m) {
ban[nx][ny] = true;
}
}
dp[0][0] = 1;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
if (ban[i][j]) continue;
if (i == 0 && j == 0) continue;
if (i > 0) dp[i][j] += dp[i - 1][j];
if (j > 0) dp[i][j] += dp[i][j - 1];
}
}
cout << dp[n][m];
return 0;
}
⚠️ 易错点
❌ 1. 把坐标理解反
题目坐标：
通常直接用：
即可，不要交换。
❌ 2. 忘记标记马本身
马所在点也不能走：
❌ 3. 起点重复计算
之后循环时跳过它。
❌ 4. 用 int 爆掉
必须：