Luogu P1002 [NOIP 2002 普及组] 过河卒 - FFangMouRen 的小小博客ヽ( ^ω^ ゞ )

思路：

标记马的控制点：
- 定义9个偏移量（包括马自身位置和8个跳跃位置）
- 遍历这些偏移量，标记棋盘上所有马的控制点
初始化起点：
- 如果起点(0,0)不是马的控制点，则初始路径数为1；否则为0
动态规划计算路径数：
- 遍历棋盘上每个点(i,j)
- 如果是马的控制点则跳过
- 否则累加上方和左方的路径数（如果这些点可到达）
- 状态转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]
输出结果：
- 终点(n,m)的dp值就是从起点到终点的所有路径数

记得注意：

使用long long防止路径数过大导致溢出
数组大小设置为25（题目最大坐标为20）
确保不会访问到负索引（通过i>0和j>0的条件判断）

上代码！！！

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m, hx, hy;
    cin >> n >> m >> hx >> hy;

    vector<vector<bool>> ban(25, vector<bool>(25, false));
    vector<vector<long long>> dp(25, vector<long long>(25, 0));

    // 马的控制点偏移量
    int dx[] = {0, 1, 1, -1, -1, 2, 2, -2, -2};
    int dy[] = {0, 2, -2, 2, -2, 1, -1, 1, -1};

    // 标记马的控制点
    for (int i = 0; i < 9; i++) {
        int nx = hx + dx[i];
        int ny = hy + dy[i];
        if (nx >= 0 && ny >= 0) {
            ban[nx][ny] = true;
        }
    }

    // 初始化起点
    if (!ban[0][0]) dp[0][0] = 1;

    // 动态规划计算路径数
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (ban[i][j]) continue;  // 跳过马的控制点
            
            // 从上方的点走来
            if (i > 0 && !ban[i-1][j]) 
                dp[i][j] += dp[i-1][j];
                
            // 从左方的点走来
            if (j > 0 && !ban[i][j-1]) 
                dp[i][j] += dp[i][j-1];
        }
    }

    cout << dp[n][m] << endl;

    return 0;
}

评论