企业官网建设流程全解析

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 问题重述与关键约束

让我们先把问题用更精确的语言描述一遍，并明确所有约束条件，这是写出正确代码的第一步。

已知条件：

1. 棋盘坐标系：通常设定A点为原点(0,0)，B点为(n, m)。n和m是不超过20的正整数（根据NOIP原题，实际实现时我们可以处理更大的范围）。
2. 卒的移动规则：每次只能向右（x坐标+1）或向下（y坐标+1）移动一格。这意味着路径不能回头，不能向左或向上走。
3. 马的控制点：在点C(x_horse, y_horse)上有一个马。按照中国象棋规则，马走“日”字。因此，马的控制点包括马自身所在点，以及其八个攻击点，坐标偏移量为：(±2, ±1)和(±1, ±2)的所有组合。卒子不能踏入这些控制点。
4. 输入与输出：通常输入三个点的坐标（或直接给出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]这个公式时，当i=0或j=0时会访问dp[-1][j]或dp[i][-1]，这是非法的数组索引。因此，我们需要处理棋盘的上边界和左边界。

• 上边界（第一行，i=0）：卒子只能从左边来，因为不可能从上面来（上面没有格子）。所以对于j>0的点(0, j)，有：dp[0][j] = dp[0][j-1]前提是(0, j)点可通行。
• 左边界（第一列，j=0）：同理，卒子只能从上面来。所以对于i>0的点(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; }

逐行解析与关键点：

1. 数组大小与类型：dp数组使用long long。这是非常重要的！因为当棋盘较大时（比如20x20），路径总数会是一个非常大的数字，用int很可能溢出导致结果错误。horse数组用bool类型，节省空间。
2. 马的控制点数组dirs：这里包含了9个方向，第一个{0,0}代表马自身的位置。这是正确的，必须包含。
3. 标记控制点时的边界检查：if (nx >= 0 && nx <= bx && ny >= 0 && ny <= by)。这一步至关重要。马的控制点可能跳出棋盘范围（比如马在(0,0)附近，它的某些控制点坐标可能为负）。我们只标记棋盘范围内的点，否则在后续访问数组时会越界。
4. 起点检查：在初始化dp[0][0]=1之前，先判断起点是否被马控制。如果是，则整个问题无解，直接输出0并结束程序。这是一个必要的鲁棒性检查。
5. 递推循环：
   • 循环从i=0, j=0开始。
   • if (i == 0 && j == 0) continue;跳过起点，因为它的值我们已经明确赋予了。
   • 接着判断当前点是否为马的控制点，如果是，dp[i][j]=0，并且continue跳过状态转移。这里有个细节：即使这个点是控制点，我们将其dp值设为0也是正确的，因为它不可达。同时，它为0也保证了后续点无法从它这里获得路径数（0加任何数不影响结果）。
   • 状态转移时，用if (i>0)和if (j>0)来保护数组访问不越界。对于第一行(i==0)，只有j>0的条件成立，执行dp[0][j] += dp[0][j-1]，这正好对应了上边界条件。第一列同理。
6. 输出：直接输出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; }

优化点解析：

1. 二合一数组：dp数组身兼两职。dp[i][j] >= 0时表示路径数，dp[i][j] == -1时表示该点是马的控制点（障碍）。这节省了一个数组的空间。
2. 转移条件增强：在状态转移时，不仅检查索引i>0或j>0，还检查来源点dp[i-1][j]或dp[i][j-1]是否不等于-1。如果来源点是障碍，则不能从那里过来，贡献的路径数为0。这个判断逻辑上是严密的。
3. 提前终点检查：在开始递推前，不仅检查起点，也检查终点是否为障碍。如果终点本身就是马的控制点，那么路径数肯定为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 j=0; j<=by; ++j) for (int i=0; i<=bx; ++i)，即先列后行，这在某些情况下可能也是可行的，但不如先行后列直观，且处理边界时要小心。最稳妥、最符合思维习惯的顺序就是for (int i=0; i<=bx; ++i) for (int j=0; j<=by; ++j)。

排查与解决：

• 症状：结果错误，但小数据可能对，大数据错。或者调试时发现dp数组的值不符合预期（比如本该有值的地方是0）。
• 解决：统一使用“从上到下，从左到右”的遍历顺序。这是最标准的二维DP填表顺序。
• 调试技巧：在递推循环内部，打印出i, j, dp[i][j]的值，或者在整个循环结束后打印整个dp数组。对比手动计算的结果，很容易发现哪里出了问题。

4.5 初始化不完整

dp[0][0] = 1是起点的初始化。对于第一行和第一列的其他点，它们的状态转移依赖于边界外的点（索引为-1），我们在代码中用if (i>0)和if (j>0)来保护。但这里有一个细微之处：如果第一行或第一列上的某个点是马的控制点，它会被设为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)，i==0，所以if(i>0)不成立，if(j>0)成立，执行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。在计算第一行(i=0)时，if(i>0)条件不成立，所以只从左方累加，这是正确的。

5.3 大数处理与高精度

题目给定的n, m通常不超过20，路径数用long long足以应付。但如果棋盘变得非常大（比如100x100），路径数将是一个天文数字，远超long long的范围。这时就需要用到高精度计算（大整数运算）。我们可以用数组或字符串来表示大整数，并实现大整数的加法。将dp数组的元素类型从long long改为一个自定义的大整数类或vector<int>（每位存储一个数字），然后在状态转移时调用大整数加法函数。

// 伪代码思路 vector<int> dp[MAX][MAX]; // 每个dp[i][j]是一个存储大整数的vector // 大整数加法函数 vector<int> addBigInt(const vector<int>& a, const vector<int>& 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(x+1, y) + dfs(x, y+1)。（因为只能向右或向下）
• 为了避免重复计算，用一个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(x+1, y, bx, by) + dfs(x, y+1, 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问题（如背包问题、最长上升子序列、编辑距离等）打下了坚实的基础。下次当你遇到一个看似复杂的新问题时，不妨想想：我能不能像分析过河卒一样，定义出它的“状态”，并找到状态之间是如何“转移”的？