1. 项目概述从棋盘游戏到经典算法最近在带几个刚入门C和算法的同学做练习发现“过河卒”这个问题出现的频率相当高无论是学校的OJ、蓝桥杯的历年真题还是各种算法社区的练习题它都是一个绕不开的经典。很多新手一看到“马的控制点”、“路径条数”这些词就有点发怵觉得涉及棋盘、规则肯定很复杂。其实不然这恰恰是一个理解动态规划思想特别是其入门形式——递推——的绝佳例题。它用非常直观的二维棋盘场景把“状态定义”和“状态转移”这两个核心概念展现得淋漓尽致。简单来说这个问题描述了一个象棋棋盘上的场景一个小卒从棋盘左下角A点(0,0)出发要走到右上角B点(n, m)。卒子的行走规则很朴素每次只能向右或向下走一格。但麻烦在于棋盘上还有一个对方的马位置在C点这个马本身以及它一步能跳到的所有位置即“马的控制点”或“马脚点”是禁止卒子通行的。我们的任务就是计算出在避开这些禁止点的前提下卒子从A点到B点一共有多少条不同的行走路径。这听起来是不是有点像我们小时候做的“寻路”或“计数”问题只不过加上了几个障碍点。解决它的核心武器就是递推。我们不需要让卒子真的去“走”遍所有可能而是用一种更聪明的方式站在终点B点回头看到达B点的路径必然是从其左边的点(n, m-1)走过来或者从其上面的点(n-1, m)走过来。那么到达B点的路径总数自然就等于到达左边点的路径数加上到达上面点的路径数。这个关系就是状态转移方程。我们从起点A(0,0)开始这里有一条虚拟路径利用这个方程像铺地毯一样一行一行、一列一列地计算出到达棋盘上每个可通行点的路径数最终递推到B点答案就出来了。理解并实现这个算法不仅能帮你解决这一道题更能为你打开动态规划的大门。你会发现很多看似复杂的问题比如背包问题、最长公共子序列等其内核思想和这种“棋盘递推”是相通的。接下来我将彻底拆解这个问题从问题分析、递推公式推导到C代码的逐行实现、边界处理以及我调试过程中踩过的坑和总结的技巧手把手带你吃透它。2. 核心思路与递推公式推导2.1 问题重述与关键约束让我们先把问题用更精确的语言描述一遍并明确所有约束条件这是写出正确代码的第一步。已知条件棋盘坐标系通常设定A点为原点(0,0)B点为(n, m)。n和m是不超过20的正整数根据NOIP原题实际实现时我们可以处理更大的范围。卒的移动规则每次只能向右x坐标1或向下y坐标1移动一格。这意味着路径不能回头不能向左或向上走。马的控制点在点C(x_horse, y_horse)上有一个马。按照中国象棋规则马走“日”字。因此马的控制点包括马自身所在点以及其八个攻击点坐标偏移量为(±2, ±1)和(±1, ±2)的所有组合。卒子不能踏入这些控制点。输入与输出通常输入三个点的坐标或直接给出B点坐标和马坐标输出一个整数即从A到B的路径总数。一个至关重要的隐含条件由于卒只能向右或向下走这意味着整个路径规划是一个有向无环的过程。我们永远不会走回头路这保证了我们可以用从起点开始的递推方式来求解而不会陷入循环。2.2 递推思想与状态定义动态规划/递推的核心是定义“状态”并找到状态之间的关系。在这个问题里“状态”非常直观。我们定义一个二维数组dp[i][j]。状态含义dp[i][j]表示从起点A(0,0)走到点(i, j)的所有可能路径的总数。状态表示这里i和j对应棋盘的x坐标和y坐标。为了编程方便我们通常让数组下标与坐标直接对应。那么我们最终要求解的目标就是dp[n][m]。2.3 状态转移方程推导现在思考卒子要走到(i, j)点它最后一步是从哪里来的 根据移动规则它只能从正上方(i-1, j)走过来或者从正左方(i, j-1)走过来。不可能从其他方向来。因此到达(i, j)点的路径数就等于到达(i-1, j)的路径数加上到达(i, j-1)的路径数。用公式表示就是dp[i][j] dp[i-1][j] dp[i][j-1]这就是我们最核心的状态转移方程。2.4 边界条件与初始化递推需要一个起点。我们的起点是A(0,0)。那么dp[0][0]应该是多少 从(0,0)到(0,0)本身不需要移动我们可以认为存在1条路径即不走的路径。所以dp[0][0] 1但是直接使用dp[i][j] dp[i-1][j] dp[i][j-1]这个公式时当i0或j0时会访问dp[-1][j]或dp[i][-1]这是非法的数组索引。因此我们需要处理棋盘的上边界和左边界。上边界第一行i0卒子只能从左边来因为不可能从上面来上面没有格子。所以对于j0的点(0, j)有dp[0][j] dp[0][j-1]前提是(0, j)点可通行。左边界第一列j0同理卒子只能从上面来。所以对于i0的点(i, 0)有dp[i][0] dp[i-1][0]前提是(i, 0)点可通行。马的控制点处理如果点(i, j)是马的控制点那么卒子根本不能到达这里。因此在计算dp[i][j]之前我们必须先判断该点是否被马控制。如果是则直接设置dp[i][j] 0并且这个点也不能作为后续点路径的来源。在代码实现中我们通常在初始化阶段就标记出所有马的控制点然后在递推计算时如果当前点是控制点就跳过状态转移直接赋值为0。注意这里有一个初学者极易忽略的大坑马的控制点包括马本身所在的位置C点。这意味着如果起点A(0,0)或终点B(n,m)恰好是马的控制点根据题目C≠A且C≠B所以起点终点本身不会是马但有可能被马“踩住”那么路径数直接就是0。在代码中必须做这个检查。2.5 递推方向由于状态转移方程dp[i][j]依赖于dp[i-1][j]上方和dp[i][j-1]左方这意味着在计算dp[i][j]时它左边和上方的状态必须已经计算出来。 因此最自然的递推顺序就是从上到下i从0到n从左到右j从0到m逐行或逐列计算。这样就能保证在计算每个点时它所依赖的两个子状态都是已知的。3. 代码实现与逐行解析理论清晰了我们动手用C实现。我会提供两个版本的代码一个是最直观、易于理解的版本另一个是进行了空间和逻辑优化的版本。我们先从基础版开始。3.1 基础实现版本这个版本严格遵循上面的思路定义两个二维数组一个用于DP一个用于标记马的控制点。#include iostream #include cstring // 使用memset初始化数组 using namespace std; // 马可以跳到的8个方向加上自身位置共9个点 const int dirs[9][2] { {0, 0}, // 马自身 {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, // 马走日的四个正向方向 {2, -1}, {1, -2}, {-1, -2}, {-2, -1} // 马走日的四个反向方向 }; int main() { // 输入终点B的坐标 (bx, by) 马的位置 (hx, hy) int bx, by, hx, hy; cin bx by hx hy; // 定义DP数组和标记数组。为了下标与坐标直接对应数组大小多开一些防止越界。 // 这里开到25足以应对题目要求的20以内并留有余量。 long long dp[25][25] {0}; // 路径数可能很大用long long防止溢出 bool horse[25][25] {false}; // 标记是否为马的控制点 // 1. 标记马的控制点 for (int i 0; i 9; i) { int nx hx dirs[i][0]; int ny hy dirs[i][1]; // 检查坐标是否在棋盘范围内0到bx, 0到by if (nx 0 nx bx ny 0 ny by) { horse[nx][ny] true; } } // 2. 初始化起点 // 如果起点就是马的控制点虽然题目说C≠A但A点可能被马“控制”则直接输出0 if (horse[0][0]) { cout 0 endl; return 0; } dp[0][0] 1; // 起点路径数为1 // 3. 动态规划递推 for (int i 0; i bx; i) { for (int j 0; j by; j) { // 跳过起点因为起点已经初始化 if (i 0 j 0) continue; // 如果当前点是马的控制点不可达路径数为0 if (horse[i][j]) { dp[i][j] 0; continue; } // 状态转移 if (i 0) { // 可以从上方来 dp[i][j] dp[i-1][j]; } if (j 0) { // 可以从左方来 dp[i][j] dp[i][j-1]; } } } // 4. 输出结果 cout dp[bx][by] endl; return 0; }逐行解析与关键点数组大小与类型dp数组使用long long。这是非常重要的因为当棋盘较大时比如20x20路径总数会是一个非常大的数字用int很可能溢出导致结果错误。horse数组用bool类型节省空间。马的控制点数组dirs这里包含了9个方向第一个{0,0}代表马自身的位置。这是正确的必须包含。标记控制点时的边界检查if (nx 0 nx bx ny 0 ny by)。这一步至关重要。马的控制点可能跳出棋盘范围比如马在(0,0)附近它的某些控制点坐标可能为负。我们只标记棋盘范围内的点否则在后续访问数组时会越界。起点检查在初始化dp[0][0]1之前先判断起点是否被马控制。如果是则整个问题无解直接输出0并结束程序。这是一个必要的鲁棒性检查。递推循环循环从i0, j0开始。if (i 0 j 0) continue;跳过起点因为它的值我们已经明确赋予了。接着判断当前点是否为马的控制点如果是dp[i][j]0并且continue跳过状态转移。这里有个细节即使这个点是控制点我们将其dp值设为0也是正确的因为它不可达。同时它为0也保证了后续点无法从它这里获得路径数0加任何数不影响结果。状态转移时用if (i0)和if (j0)来保护数组访问不越界。对于第一行(i0)只有j0的条件成立执行dp[0][j] dp[0][j-1]这正好对应了上边界条件。第一列同理。输出直接输出dp[bx][by]。这个版本逻辑清晰非常适合理解。但它使用了两个二维数组。我们是否可以优化3.2 优化实现版本优化主要在两个地方空间优化和逻辑合并。空间优化我们注意到在标记马的控制点时其实可以直接在dp数组上操作用一个特殊值比如-1来表示该点是障碍点马的控制点。这样就能省去一个horse数组。但为了代码清晰我们保留horse数组的讲解实际比赛中用特殊值标记也是常见技巧。逻辑合并我们可以把边界条件和状态转移更优雅地写在一起。同时将马的控制点判断集成到递推循环中。#include iostream #include cstring using namespace std; const int dirs[9][2] {{0,0}, {-2,1}, {-1,2}, {1,2}, {2,1}, {2,-1}, {1,-2}, {-1,-2}, {-2,-1}}; int main() { int bx, by, hx, hy; cin bx by hx hy; long long dp[25][25]; // 初始化dp数组为0 memset(dp, 0, sizeof(dp)); // 标记马的控制点为-1表示不可达 for (int i 0; i 9; i) { int nx hx dirs[i][0]; int ny hy dirs[i][1]; if (nx 0 nx bx ny 0 ny by) { dp[nx][ny] -1; // 用-1表示障碍 } } // 检查起点和终点 if (dp[0][0] -1 || dp[bx][by] -1) { cout 0 endl; return 0; } // 初始化起点 dp[0][0] 1; // 动态规划递推 for (int i 0; i bx; i) { for (int j 0; j by; j) { if (i 0 j 0) continue; // 起点已处理 if (dp[i][j] -1) { // 如果是马的控制点保持-1在计算来源时会跳过 continue; } // 状态转移从上边来 if (i 0 dp[i-1][j] ! -1) { dp[i][j] dp[i-1][j]; } // 状态转移从左边来 if (j 0 dp[i][j-1] ! -1) { dp[i][j] dp[i][j-1]; } } } // 输出结果如果终点被标记为-1上面检查已经返回0所以这里dp[bx][by]一定是非负数 cout dp[bx][by] endl; return 0; }优化点解析二合一数组dp数组身兼两职。dp[i][j] 0时表示路径数dp[i][j] -1时表示该点是马的控制点障碍。这节省了一个数组的空间。转移条件增强在状态转移时不仅检查索引i0或j0还检查来源点dp[i-1][j]或dp[i][j-1]是否不等于-1。如果来源点是障碍则不能从那里过来贡献的路径数为0。这个判断逻辑上是严密的。提前终点检查在开始递推前不仅检查起点也检查终点是否为障碍。如果终点本身就是马的控制点那么路径数肯定为0直接返回。这是一个很好的提前终止优化。个人心得在算法竞赛或时间敏感的场景下第二个优化版本是更常用的写法。它更简洁且减少了一次数组访问。但对于初学者我强烈建议从第一个版本开始理解因为它将“数据”路径数和“状态标记”是否障碍分离概念上更清晰调试时也更容易观察中间状态。你可以通过打印整个dp数组来可视化递推过程这对于理解动态规划非常有帮助。4. 调试技巧与常见问题排查即便思路清晰代码写出来也可能遇到各种问题。下面是我在实现和教学过程中总结的几个常见“坑”及其解决方法。4.1 路径数溢出为什么必须用long long这是最容易忽略的问题。我们来看一个例子假设棋盘是20x20且没有马阻拦。从(0,0)到(20,20)的路径数是多少这实际上是一个组合数学问题卒子需要向右走20步向下走20步总共40步其中选择20步向右或向下即可。路径总数为 C(40, 20)。计算一下 C(40, 20) 40! / (20! * 20!) ≈ 1.378e11 这个数字远远超过了int类型能表示的最大值约21亿2.1e9。如果用int存储会发生溢出导致结果变成负数或一个错误的数值。排查与解决症状输入较小的数据结果正确输入较大的数据如15x15以上结果明显不对甚至为负数。解决毫不犹豫地将dp数组的类型声明为long long。在C中long long至少是64位表示范围大约在 ±9.2e18足够应对此类问题。检查点确保所有与路径数相关的变量包括循环中的临时累加都是long long类型。4.2 数组越界马的控制点标记这是导致程序运行时崩溃如“Segmentation fault”的常见原因。问题场景马的位置在棋盘边缘例如在(0,0)。那么它的控制点(-2, 1),(-1, 2)等其x坐标或y坐标就是负数。如果我们用horse[nx][ny] true或dp[nx][ny] -1而不加检查就会访问horse[-2][1]这样的非法内存地址。排查与解决症状程序在输入某些特定数据尤其是马在边界时直接崩溃。解决在标记马的控制点时必须加上边界判断。if (nx 0 nx bx ny 0 ny by) { // 只有点在棋盘范围内才进行标记 horse[nx][ny] true; // 或 dp[nx][ny] -1; }检查点dirs数组中的9个偏移量每一个都可能产生越界坐标。务必对每个计算出的(nx, ny)进行范围校验。4.3 起点/终点是马的控制点题目明确说明C≠A且C≠B意思是马的位置不等于A点或B点。但是马的控制点是包含马自身及其8个攻击点的。所以完全有可能A点或B点正好被马“踩住”即位于马的攻击点上。例如A(0,0)马在(2,1)那么A点就是马的控制点之一对应偏移(-2, -1)。问题场景如果起点就是马的控制点卒子一开始就无法移动路径数为0。如果终点是马的控制点卒子永远到不了终点路径数也为0。如果不做这个检查程序可能会错误地计算出非零值。排查与解决症状对于某些明显无解的测试用例如上述例子程序输出了一个非0的正整数。解决在初始化dp[0][0]之前先判断起点是否为控制点。在计算完dp数组后或者更早地在标记完控制点后判断终点是否为控制点。如果是直接输出0。// 标记完所有控制点后... if (horse[0][0] || horse[bx][by]) { // 使用horse数组的版本 cout 0 endl; return 0; }4.4 递推顺序与依赖关系递推必须保证在计算dp[i][j]时dp[i-1][j]和dp[i][j-1]已经计算完毕。错误示例如果使用两重循环但顺序是for (int j0; jby; j) for (int i0; ibx; i)即先列后行这在某些情况下可能也是可行的但不如先行后列直观且处理边界时要小心。最稳妥、最符合思维习惯的顺序就是for (int i0; ibx; i) for (int j0; jby; j)。排查与解决症状结果错误但小数据可能对大数据错。或者调试时发现dp数组的值不符合预期比如本该有值的地方是0。解决统一使用“从上到下从左到右”的遍历顺序。这是最标准的二维DP填表顺序。调试技巧在递推循环内部打印出i, j, dp[i][j]的值或者在整个循环结束后打印整个dp数组。对比手动计算的结果很容易发现哪里出了问题。4.5 初始化不完整dp[0][0] 1是起点的初始化。对于第一行和第一列的其他点它们的状态转移依赖于边界外的点索引为-1我们在代码中用if (i0)和if (j0)来保护。但这里有一个细微之处如果第一行或第一列上的某个点是马的控制点它会被设为0。这没问题。但是在这个控制点之后的点呢例如第一行上点(0,2)是马的控制点dp[0][2]0。那么点(0,3)的路径数应该是多少根据公式dp[0][3] dp[0][2] dp[-1][3]。dp[-1][3]不存在所以只考虑dp[0][2]。因为dp[0][2]0所以dp[0][3]也应该为0。这意味着一旦第一行或第一列上出现一个控制点这个点之后的所有点因为只能从左边或上面来都将不可达。我们的代码能正确处理这种情况吗在基础版本中对于点(0,3)i0所以if(i0)不成立if(j0)成立执行dp[0][3] dp[0][2]。由于dp[0][2]之前被设为0所以dp[0][3]正确地为0。在优化版本中我们判断了dp[i-1][j] ! -1和dp[i][j-1] ! -1如果来源点是障碍-1我们就不加。对于(0,3)来源点(0,2)是-1所以dp[0][3]得不到任何累加保持初始值0。两种写法都是正确的。关键点在于dp数组必须被正确初始化为0。在C中全局数组或静态数组会自动初始化为0但局部数组不会。因此在函数内部声明dp数组后务必用memset或循环将其所有元素初始化为0。这是很多错误的根源。long long dp[25][25] {0}; // 正确的初始化方式 // 或者 long long dp[25][25]; memset(dp, 0, sizeof(dp)); // 也是正确的5. 算法扩展与思维提升掌握了基础解法后我们可以思考一些变种和扩展这能极大加深对动态规划的理解。5.1 如果卒可以向左、向上走原题中卒只能向右或向下这保证了递推的无后效性当前状态只依赖于左边和上边的状态。如果允许卒向四个方向上、下、左、右移动但马的控制点依然存在问题就变成了在带障碍的网格图中求两点间所有路径的数量。注意是“所有路径”不是“最短路径”。由于可以来回走路径数量可能是无限的如果存在一个不经过控制点的环。因此这个问题通常会被加上其他限制比如“每个格子只能经过一次”这就变成了一个**回溯搜索DFS**问题不能用简单的递推解决了。动态规划适用于有向无环图DAG而允许四向移动且可重复访问的网格图可能存在环。5.2 使用滚动数组进行空间优化我们当前的dp数组是二维的大小O(nm)。观察状态转移方程dp[i][j] dp[i-1][j] dp[i][j-1]在计算第i行时我们只依赖于第i-1行和当前行已计算的部分第j-1列。因此我们可以只用两个一维数组一个表示上一行prev一个表示当前行curr将空间复杂度从O(nm)优化到O(m)。long long prev[25] {0}; long long curr[25] {0}; bool horse[25][25] {false}; // ... 标记horse数组 ... if (horse[0][0]) { cout 0 endl; return 0; } prev[0] 1; // 初始化第一行实际上是第0行的“上一行” for (int i 0; i bx; i) { // 计算当前行 curr for (int j 0; j by; j) { if (horse[i][j]) { curr[j] 0; continue; } long long ways 0; if (i 0) ways prev[j]; // 从上方来即上一行的第j列 if (j 0) ways curr[j-1]; // 从左方来即当前行的第j-1列 curr[j] ways; } // 将当前行设置为“上一行”为下一轮做准备 swap(prev, curr); // 注意交换后新的“当前行”curr需要被清零吗不一定因为下一轮会覆盖所有元素。 // 但安全起见可以在swap后加一句 memset(curr, 0, sizeof(curr)); } // 循环结束后结果在 prev[by] 里因为最后进行了一次swap cout prev[by] endl;注意使用滚动数组时对马的控制点的判断需要小心。horse数组仍然是二维的我们需要根据当前坐标(i,j)来查询。同时初始化prev[0]1的逻辑对应于dp[0][0]1。在计算第一行(i0)时if(i0)条件不成立所以只从左方累加这是正确的。5.3 大数处理与高精度题目给定的n, m通常不超过20路径数用long long足以应付。但如果棋盘变得非常大比如100x100路径数将是一个天文数字远超long long的范围。这时就需要用到高精度计算大整数运算。我们可以用数组或字符串来表示大整数并实现大整数的加法。将dp数组的元素类型从long long改为一个自定义的大整数类或vectorint每位存储一个数字然后在状态转移时调用大整数加法函数。// 伪代码思路 vectorint dp[MAX][MAX]; // 每个dp[i][j]是一个存储大整数的vector // 大整数加法函数 vectorint addBigInt(const vectorint a, const vectorint b) { // ... 实现大整数相加 ... } // 在状态转移时 dp[i][j] addBigInt(dp[i-1][j], dp[i][j-1]);这对于算法竞赛的进阶题目是一个很好的练习。5.4 从递推到记忆化搜索我们目前采用的是“自底向上”的递推迭代方法。还有一种等价的“自顶向下”的递归方法称为记忆化搜索Memoization。思路是定义一个递归函数dfs(x, y)表示从(x, y)走到终点(bx, by)的路径数。那么如果(x, y)是马的控制点或越界返回0。如果(x, y)就是终点(bx, by)返回1。否则dfs(x, y) dfs(x1, y) dfs(x, y1)。因为只能向右或向下为了避免重复计算用一个memo[x][y]数组记录已经计算过的dfs(x, y)的值。long long memo[25][25]; bool horse[25][25]; long long dfs(int x, int y, int bx, int by) { // 越界或被马控制 if (x bx || y by || horse[x][y]) return 0; // 到达终点 if (x bx y by) return 1; // 已经计算过 if (memo[x][y] ! -1) return memo[x][y]; // 递归计算并记忆 memo[x][y] dfs(x1, y, bx, by) dfs(x, y1, bx, by); return memo[x][y]; } int main() { // ... 输入、标记horse ... memset(memo, -1, sizeof(memo)); // 初始化为-1表示未计算 cout dfs(0, 0, bx, by) endl; return 0; }记忆化搜索的代码往往更直观更符合人的思维从起点开始探索所有可能路径。它和递推在时间复杂度上是相同的都是O(n*m)但会有递归调用的开销。对于这个问题递推更高效但对于一些状态转移复杂的DP记忆化搜索可能是更简单的实现方式。6. 实战测试与案例理论说再多不如跑几个例子。我准备了几个典型的测试用例你可以用它们来验证你的程序。测试用例1基础案例输入6 6 3 3解释终点B(6,6)马在(3,3)。马的控制点包括(3,3), (1,2), (1,4), (2,1), (2,5), (4,1), (4,5), (5,2), (5,4)。 预期输出你需要运行程序得到结果。你可以尝试手动计算或画个小图辅助理解。测试用例2马在起点旁输入4 8 2 4解释这就是我们参考文章中的例子。终点B(4,8)马在(2,4)。你可以用我们代码中的打印功能如果添加了输出dp数组与参考文章的结果进行对比。测试用例3马堵住关键路径输入3 3 1 1解释马在中心(1,1)它的控制点几乎覆盖了棋盘中心区域。计算一下到达(3,3)的路径。你可以先在心里估算一下可能路径数很少。测试用例4大棋盘测试输入20 20 10 10解释测试long long是否溢出以及程序效率。路径数会非常大。测试用例5边界情况输入0 0 2 1解释终点就是起点(0,0)。根据规则马的位置C≠A所以马不在(0,0)。但马的控制点可能包含(0,0)吗计算一下。如果起点被控制输出应为0否则为1从起点到起点有一条路径。测试用例6无马情况输入5 5 -1 -1或者输入一个不在棋盘上的马坐标如10 10但需修改程序允许输入-1 解释如果没有马这就是一个简单的组合问题路径数应为C(10,5)252。你可以用这个测试来验证状态转移公式是否正确。在编写完代码后务必用这些用例进行测试。特别是边界情况往往是程序出错的重灾区。调试时除了看最终结果更有效的方法是打印出整个dp数组或者horse数组与你的手动推导进行比对能快速定位逻辑错误。最后过河卒问题虽然规则简单但它完美地诠释了动态规划中“状态”、“状态转移方程”、“边界条件”、“无后效性”等核心概念。理解它就为你解决更复杂的DP问题如背包问题、最长上升子序列、编辑距离等打下了坚实的基础。下次当你遇到一个看似复杂的新问题时不妨想想我能不能像分析过河卒一样定义出它的“状态”并找到状态之间是如何“转移”的