NOIP2002普及组过河卒（洛谷1002）：用动态规划解决经典棋盘路径问题
引言
动态规划是算法竞赛中的重要技巧，它能有效解决许多计数类问题。今天我们就以洛谷P1002"过河卒"为例，详细讲解如何用动态规划解决棋盘路径计数问题。
一、问题重述
在一个(n+1)×(m+1)的棋盘上：
卒子从(0,0)出发，只能向右或向下移动
棋盘上有一个敌方的马，马所在位置及其8个控制点是禁区
需要计算卒子安全到达(n,m)的所有路径数
二、解题思路详解
马的控制点确定：
马走"日"字，有8个可能的控制点
需要检查这些点是否在棋盘范围内
动态规划表设计：
dp[i][j]表示到达点(i,j)的路径数
如果(i,j)是控制点，则dp[i][j]=0
否则dp[i][j] = dp[i-1][j] + dp[i][j-1]
边界条件处理：
起点dp[0][0]初始化为1（如果不是控制点）
第一行和第一列需要特殊处理，因为它们只有一种到达方式
三、实现解析
输入处理：
读取终点坐标(n,m)和马的位置(horse_x, horse_y)
控制点标记：
使用二维数组blocked标记所有禁区
包括马的位置及其8个控制点
动态规划初始化：
初始化起点dp[0][0]
处理第一行和第一列的特殊情况
动态规划计算：
双重循环填充dp表
根据状态转移方程计算每个点的路径数
输出结果：
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; }
五、常见错误
数组越界：
没有检查马的控制点是否在棋盘范围内
访问dp表时越界
初始化错误：
忘记处理起点是控制点的情况
第一行或第一列的处理不正确
数据类型不足：
使用int可能导致溢出
应该使用long long存储路径数
六、扩展思考
这个问题可以有很多变种：
卒子可以向上、下、左、右移动（变成标准网格行走问题）
马可以移动（动态变化的控制点）
棋盘上有多个马或其他障碍物
求最短路径而非路径计数
七、结论
通过这个问题的分析，我们学习了：
如何用动态规划解决路径计数问题
如何处理棋盘类问题的边界条件
如何标记和管理禁区点
动态规划表的构建和填充方法
掌握这些技巧对解决类似的算法问题非常有帮助。
原创内容 转载请注明出处
