每日c/c++题 备战蓝桥杯(P1002 [NOIP 2002 普及组] 过河卒)

洛谷P1002 [NOIP 2002 普及组] 过河卒 题解

题目描述

过河卒是一道经典的动态规划题目。题目大意是：一个卒子从棋盘左上角(0,0)出发，要走到右下角(n,m)，棋盘上有一个马在(x,y)位置，卒子不能经过马所在位置及其周围8个位置。求卒子的合法路径总数。

解题思路

1. 问题分析

• 棋盘范围：棋盘为(n+1)×(m+1)的网格（坐标从0开始）
• 移动规则：卒子只能向右或向下移动
• 阻挡条件：马的位置及其控制的8个位置不可达
• 核心目标：统计从起点到终点的所有合法路径数

2. 动态规划建模

状态定义

dp[i][j]表示从起点(0,0)到达坐标(i,j)的合法路径总数

状态转移

$$dp[i][j]=\{\begin{array}{ll}0& \text{当前位置被马控制}\\ 1& \text{i=0且j=0（起点）}\\ dp[i-1][j]+dp[i][j-1]& \text{其他情况}\end{array}$$

初始化条件

• dp[0][0] = 1（起点自身算1条路径）
• 被马控制的位置及其后续位置保持0值

3. 关键优化

坐标系偏移

将原始坐标系整体右移2格，下移2格（代码中b1 += 2; b2 += 2），目的是：

1. 避免处理负数坐标
2. 统一处理棋盘边界（通过循环条件i <= b1和j <= b2自动限制范围）

马控制范围判断

通过预定义的8个方向向量：

int dx[8] = {-2,-2,-1,+1,+2,+2,+1,-1};
int dy[8] = {-1,+1,+2,+2,+1,-1,-2,-2};

检查目标位置是否被马控制：

bool pd(int a, int b) {
    // 检查马本体位置
    if (m1 == a && m2 == b) return false;
    // 检查8个控制位
    for (int i = 0; i < 8; ++i) {
        if (m1 + dx[i] == a && m2 + dy[i] == b) return false;
    }
    return true;
}

代码解析

1. 输入处理

cin >> b1 >> b2 >> m1 >> m2;
b1 += 2;  // 扩展后的棋盘行数
b2 += 2;  // 扩展后的棋盘列数
m1 += 2;  // 马坐标同步偏移
m2 += 2;

2. 动态规划核心

for (int i = 2; i <= b1; ++i) {        // 遍历所有行
    for (int j = 2; j <= b2; ++j) {    // 遍历所有列
        if (!pd(i, j)) {               // 被马控制的位置
            dp[i][j] = 0;
            continue;
        }
        if (i == 2 && j == 2) {        // 起点初始化
            dp[i][j] = 1;
            continue;
        }
        dp[i][j] = dp[i-1][j] + dp[i][j-1];  // 状态转移
    }
}

3. 输出结果

最终结果存储在dp[b1][b2]中，直接输出即可。

复杂度分析

• 时间复杂度：O(nm)，仅需遍历棋盘一次
• 空间复杂度：O(nm)，使用二维数组存储状态

常见错误及注意事项

1. 坐标偏移：忘记对马的位置进行同步偏移会导致控制范围判断错误
2. 边界条件：当马位于起点或终点时，路径数应为0
3. 数据类型：路径数可能超过int范围，需使用long long类型
4. 初始化顺序：必须按行优先顺序填充dp数组，保证状态转移的正确性

扩展思考

• 记忆化搜索：可用DFS+记忆化实现，但时间复杂度较高（O(2^(n+m))）
• 矩阵快速幂：对于无阻挡的纯路径计数问题，可用组合数学优化到O(log(n+m))
• 三维DP：当需要记录更多状态时（如不同移动方式），可扩展DP维度

总结

本题通过动态规划完美解决了路径计数问题，关键点在于：

1. 合理建模状态转移方程
2. 正确处理棋盘边界和阻挡条件
3. 通过坐标偏移简化边界判断

该方法的时间复杂度稳定在O(nm)，能够高效处理题目给定的数据范围（n,m ≤ 20），是典型的动态规划应用案例。