一、题目解读
“过河卒”是2002年NOIP普及组的经典题目（洛谷P1002），要求计算棋盘上卒从A点(0,0)到达B点(n,m)的路径条数。卒仅能向右或向下移动，但需避开马的控制点（马的位置及跳跃一步可达的点）。题目限制n、m≤20，需高效算法求解。
二、解题思路
采用动态规划（DP）。定义状态dp[i][j]为到达(i,j)点的合法路径数。核心思想是路径数由上方和左方转移而来，即dp[i][j] = dp[i-1][j] + dp[i][j-1]。需先标记马的控制点，避免路径经过禁区。
三、解题步骤
1. 输入与初始化：读入n、m及马的位置，创建dp和blocked数组标记控制点。
2. 标记控制点：通过方向数组dx,dy遍历马跳跃的8个方向，标记所有控制点。
3. 边界处理：初始化起点dp[0][0]=1，处理第一列/行路径（若不被控制，则路径数为上方/左方的累加）。
4. 动态规划循环：遍历(i,j)，若(i,j)未被控制，则更新dp[i][j]为上方和左方路径之和。
5. 输出结果：dp[n][m]即终点路径数。
四、代码与注释
#include <iostream> #include <vector> using namespace std; // 马的控制点方向 const int dx[] = {1, 1, -1, -1, 2, 2, -2, -2}; const int dy[] = {2, -2, 2, -2, 1, -1, 1, -1}; int main() {
int n, m, horse_x, horse_y;
cin >> n >> m >> horse_x >> horse_y;
// 创建棋盘并标记控制点
vector<vector<bool>> blocked(n+1, vector<bool>(m+1, false));
vector<vector<long long>> dp(n+1, vector<long long>(m+1, 0));
// 标记马的位置和控制点
blocked[horse_x][horse_y] = true;
for (int i = 0; i < 8; ++i) {
int nx = horse_x + dx[i];
int ny = horse_y + dy[i];
if (nx >= 0 && nx <= n && ny >= 0 && ny <= m) {
blocked[nx][ny] = true;
}
}
// 初始化起点
dp[0][0] = blocked[0][0]? 0 : 1;
// 处理第一列
for (int i = 1; i <= n; ++i) {
if (!blocked[i][0]) {
dp[i][0] = dp[i-1][0];
}
}
// 处理第一行
for (int j = 1; j <= m; ++j) {
if (!blocked[0][j]) {
dp[0][j] = dp[0][j-1];
}
}
// 动态规划计算路径数
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (!blocked[i][j]) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
}
cout << dp[n][m] << endl;
return 0; }五、总结
本文通过动态规划解决“过河卒”问题，重点在于状态定义、边界初始化与马的控制点处理。代码利用vector简化边界判断，结合方向数组高效标记控制点，最终实现O(nm)时间复杂度。该解法对算法竞赛中的DP问题具有参考价值。
来源：信奥自学之路