【动态规划·路径计数】GESP六级 / CSP-J 题解：luogu-P1002 [NOIP2002 普及组] 过河卒

NOIP 2002 普及组第四题，洛谷 P1002。本题是算法竞赛与考级中学习网格动态规划（Grid DP）与基础递推模型不可跨越的教科书级经典题目，被广泛收录于 GESP 六级考级（动态规划考点）及 CSP-J 普及组核心必做题单。题目核心考察障碍物标记、网格走步递推方程构造以及 64 位整型溢出防范。题目难度⭐⭐☆☆☆，洛谷难度等级普及-。

P1002 [NOIP2002 普及组] 过河卒

题目要求

题目描述

棋盘上 $A$ 点有一个过河卒，需要走到目标 $B$ 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 $C$ 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。

棋盘用坐标表示，$A$ 点 $(0, 0)$、$B$ 点 $(n, m)$，同样马的位置坐标是需要给出的。

现在要求你计算出卒从 $A$ 点能够到达 $B$ 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。

输入格式

一行四个正整数，分别表示 $B$ 点坐标和马的坐标。

输出格式

一个整数，表示所有的路径条数。

输入输出样例 #1

样例输入 #1

6 6 3 3

样例输出 #1

6

说明/提示

对于 $100\%$ 的数据，$1 \le n, m \le 20$，$0 \le$ 马的坐标 $\le 20$。

【题目来源】

NOIP 2002 普及组第四题

题目分析

1. 卒的移动规则与无后效性

题目规定卒只能向右或者向下移动。

• 如果卒当前处于棋盘坐标 $(i, j)$，那么它只可能来自其上方相邻格 $(i - 1, j)$，或者左方相邻格 $(i, j - 1)$。
• 卒到达某一个格子 $(i, j)$ 之后，它未来的移动完全不受“它是如何到达 $(i, j)$”这一历史轨迹的影响，只取决于当前坐标状态。这完全满足动态规划的核心前提——无后效性与最优子结构（在计数问题中对应加法原理子问题划分）。

2. 状态转移方程（加法原理）

设 $dp[i][j]$ 表示卒从起点 $(0, 0)$ 出发到达格子 $(i, j)$ 的合法路径总条数：

• 如果点 $(i, j)$ 是马的位置或者属于马的跳步控制点，则卒绝对无法踏足该位置，路径数为 $0$： $dp[i][j] = 0$

• 如果点 $(i, j)$ 不是控制点：

  • 起点基础状态：$dp[0][0] = 1$（若起点本身被马控制，则直接为 $0$）；
  • 普通位置：根据分类加法计数原理，到达 $(i, j)$ 的总方法数等于从左边走过来的方法数与从上边走过来的方法数之和： $dp[i][j] = dp[i - 1][j] + dp[i][j - 1]$

其中当 $i = 0$ 时无法从上方转移（无 $i - 1$），$j = 0$ 时无法从左方转移（无 $j - 1$）。

3. 对方马的 9 个控制点界定

中国象棋中“马走日字”。如果马的坐标为 $(hx, hy)$，它一步能到达的所有跳跃位置偏移量共有 $8$ 种，加上马自身所在的格子，总共有 $9$ 个点被判定为禁止通行点（控制点）：

$(dx, dy) \in \{(0, 0), (1, 2), (1, -2), (2, 1), (2, -1), (-1, 2), (-1, -2), (-2, 1), (-2, -1)\}$

我们只需要在 DP 计算前，将这 $9$ 个点在二维布尔数组中标记为 true 即可。

解题步骤与核心避坑点

1. 数组越界防范（马的控制点可能超出棋盘范围）

当马位于棋盘边缘（例如靠近 $(0, 0)$ 或 $(n, m)$）时，$hx + dx$ 或 $hy + dy$ 可能会产生负坐标或大于 $20$ 的坐标：

• 坐标必须满足 $nx \ge 0$ 且 $ny \ge 0$；
• 开辟数组时推荐开到 $25 \times 25$ 以上，杜绝越界访问非法内存。

2. 起点与终点被马控制的边界特判

• 如果马恰好在 $(0, 0)$ 或者马的控制点覆盖了起点 $(0, 0)$，卒一步都走不出去，直接输出 0；
• 如果马恰好在目标点 $(n, m)$ 或覆盖了终点，同样直接输出 0。 通过将控制点的 DP 值直接置 0 或跳过，状态转移方程可自然处理这一情况。

3. ⚠️ 核心痛点：整型溢出（必须使用 long long）

题目给出棋盘规模 $n, m \le 20$：

• 在没有马阻挡的最坏情况下，从 $(0, 0)$ 走到 $(20, 20)$ 一共需要走 $20 + 20 = 40$ 步，其中任意选 $20$ 步向右走，路径总数为组合数： $\binom{40}{20} = \frac{40!}{20! \times 20!} = 137,846,528,820 \approx 1.38 \times 10^{11}$
• 标准 32 位有符号整型 int 的最大上限为 $2^{31} - 1 = 2,147,483,647 \approx 2.14 \times 10^9$。
• $\mathbf{1.38 \times 10^{11} \gg 2.14 \times 10^9}$！如果使用 int 存储 DP 表，中途就会发生严重溢出，导致输出负数或截断错误。
• 必须将 DP 数组及计算结果全部定义为 64 位有符号整型 long long！

完整参考代码 (C++)

/**
 * Problem: luogu P1002 [NOIP2002 普及组] 过河卒
 * Algorithm: 网格动态规划 / 递推计数
 * Author: OneCoder
 */

#include <iostream>
#include <vector>

using namespace std;

// 马的跳步偏移量：包含马自身位置 (0, 0) 及 8 个日字跳跃方向
const int dx[9] = {0, 1, 1, 2, 2, -1, -1, -2, -2};
const int dy[9] = {0, 2, -2, 1, -1, 2, -2, 1, -1};

// 棋盘最大坐标 20，数组大小开到 25 避免越界
bool blocked[25][25];
long long dp[25][25]; // 核心：必须使用 long long 防止整数溢出

int main() {
    // 基础流加速
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int bx, by, hx, hy;
    if (!(cin >> bx >> by >> hx >> hy)) {
        return 0;
    }

    // 1. 预处理标记马自身位置及其 8 个跳跃控制点
    for (int i = 0; i < 9; ++i) {
        int nx = hx + dx[i];
        int ny = hy + dy[i];
        // 只有落在棋盘合法范围内的控制点才进行标记
        if (nx >= 0 && nx <= bx && ny >= 0 && ny <= by) {
            blocked[nx][ny] = true;
        }
    }

    // 2. 特殊情况判断：若起点 (0, 0) 本身被马控制，卒根本无法出发
    if (blocked[0][0]) {
        cout << 0 << "\n";
        return 0;
    }

    // 3. 初始化起点状态
    dp[0][0] = 1;

    // 4. 双重循环按拓扑序进行动态规划递推
    for (int i = 0; i <= bx; ++i) {
        for (int j = 0; j <= by; ++j) {
            // 控制点不可踏足，路径数为 0
            if (blocked[i][j]) {
                continue;
            }

            // 从上方单元格转移
            if (i > 0) {
                dp[i][j] += dp[i - 1][j];
            }
            // 从左方单元格转移
            if (j > 0) {
                dp[i][j] += dp[i][j - 1];
            }
        }
    }

    // 5. 输出到达终点 B 点的路径方案总数
    cout << dp[bx][by] << "\n";

    return 0;
}

复杂度分析

• 时间复杂度：
  • 标记马及其控制点耗时固定为 $9$ 次基本判定，为 $\mathcal{O}(1)$；
  • 棋盘状态转移双重循环次数为 $(bx + 1) \times (by + 1)$。由于 $n, m \le 20$，循环执行次数最多 $21 \times 21 = 441$ 次；
  • 总时间复杂度为 $\mathcal{O}(n \times m)$。在计算机中耗时小于 $1\text{ ms}$，瞬时完成。
• 空间复杂度：
  • 仅使用了 $25 \times 25$ 的二维布尔数组和 $25 \times 25$ 的 long long 数组，内存占用不到 $10\text{ KB}$；
  • 空间复杂度为 $\mathcal{O}(n \times m)$，远低于题目的内存限制。

总结与同类拓展

“马拦过河卒”是动态规划领域最为标准的二维网格路径转移模型。其核心套路可提炼为：

1. 确定走步基准方向与无后效性：判断是否只能单向推移（如向右、向下）；
2. 预处理障碍点（黑名单）：先将所有不可达状态进行屏蔽；
3. 加法原理状态转移：$dp[i][j] = \sum dp[\text{prev}]$；
4. 数据规模敏感度：二维网格路径问题往往伴随排列组合数的急剧爆炸，务必第一时间核算最大可能值并选用 long long 或高精度。

经典同类推荐练习题：

• luogu-P1004 [NOIP 2000 提高组] 方格取数（经典双线程网格 DP，两条路径同时走）
• luogu-P1006 [NOIP 2008 提高组] 传纸条（方格取数同源模型）
• luogu-P1176 升级版过河卒（障碍点数量大幅增加，需取模计算）
• luogu-P1044 [NOIP 2003 普及组] 栈（一维卡特兰数递推模型）