解题思路

过河卒要从 A(0,0) 走到 B(n,m)，只能向下或向右。马的位置 C(X,Y) 以及它能一步跳到的地方都不能走，问有多少条不同的走法。

第一步：找出马的控制点

马走日字，能跳到的 8 个位置是： (±1,±2) 和 (±2,±1) 的所有组合，再加上马自己站的位置。 把这些点都标记为不能走。

第二步：用递推（动态规划）数路径

设 dp[i][j] 表示从起点走到 (i,j) 有多少条路。

因为卒只能向下或向右走，所以到 (i,j) 只能从上面 (i-1,j) 或左边 (i,j-1) 过来：

dp[i][j] = dp[i-1][j] + dp[i][j-1]

规则：

• 起点的 dp[0][0] = 1
• 如果 (i,j) 是马的控制点，dp[i][j] 保持 0（走不到）
• 一层一层从上往下、从左往右算

最后 dp[n][m] 就是答案。

为什么要用 long long？ 因为格子多的时候路径数会非常大，int 会存不下。

参考代码

#include <iostream>
using namespace std;

int main() {
    int n, m, x, y;
    cin >> n >> m >> x >> y;

    // 标记马的控制点
    bool blocked[21][21] = {false};
    blocked[x][y] = true;
    // 马的 8 个跳跃位置
    int dx[8] = {1, 1, -1, -1, 2, 2, -2, -2};
    int dy[8] = {2, -2, 2, -2, 1, -1, 1, -1};
    for (int i = 0; i < 8; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && nx <= n && ny >= 0 && ny <= m) {
            blocked[nx][ny] = true;
        }
    }

    // dp[i][j] 表示从起点到 (i,j) 的路径数
    long long dp[21][21] = {0};
    if (!blocked[0][0]) dp[0][0] = 1;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            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];
        }
    }

    cout << dp[n][m] << endl;
    return 0;
}

复杂度分析

• 时间复杂度：O(N×M)，每个格子算一次
• 空间复杂度：O(N×M)，一个二维数组