【例3.6】过河卒(Noip2002)

题目描述

棋盘左上角 A(0,0) 有一只卒，只能向右或向下走到 B(n,m)（ $n,m \leqslant 20$ ）。棋盘上另有一个马 C(x,y)，马所在的点和 8 个“日字”跳跃点共 9 个控制点不能经过。求从 A 到 B 的路径条数。

思路

按到达每个格子的最后一步分类：只能从上方或左方走来。设 $f[i][j]$ 为到达 $(i,j)$ 的方案数，非控制点则 $f[i][j]=f[i-1][j]+f[i][j-1]$ ，控制点则为 0。按行从左到右递推即可，答案需用 64 位整数。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 04:41
# update_at: 2026-09-30 04:49

import sys

# 马的控制点：马自身 (0,0) 偏移 + 日字 8 个方向，一个 (dx, dy) 家族
HORSE_OFFSETS = (
    [(0, 0)]
    + [(dx, dy) for dx, dy in ((1, 2), (2, 1), (2, -1), (1, -2))]  # 右侧 4 个日字
    + [(dx, dy) for dx, dy in ((-1, -2), (-2, -1), (-2, 1), (-1, 2))]  # 左侧 4 个日字
)


def count_paths(n: int, m: int, blocked: set[tuple[int, int]]) -> int:
    """统计卒从 (0,0) 只向右/向下走到 (n,m)、避开 blocked 中马控制点的路径数。"""
    # 逐行滚动：row[j] 是到达当前行 (i, j) 的路径数
    row = [1] * (m + 1)
    for j in range(m + 1):  # 第 0 行只能一直向右，遇到控制点后右侧全部不可达
        if (0, j) in blocked:
            row[j:] = [0] * (m + 1 - j)
            break

    for i in range(1, n + 1):
        left = 0 if (i, 0) in blocked else row[0]  # 每行第 0 列只能从上面来
        row[0] = left
        for j in range(1, m + 1):
            # 上方 row[j]（还未被覆盖）+ 左方 left；控制点本身路径数为 0
            left = 0 if (i, j) in blocked else row[j] + left
            row[j] = left

    return row[m]


def solve() -> None:
    n, m, x, y = map(int, sys.stdin.buffer.read().split())
    blocked = {(x + dx, y + dy) for dx, dy in HORSE_OFFSETS}  # 马的 9 个控制点

    print(count_paths(n, m, blocked))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 09:11
 * update_at: 2026-10-05 09:12
 */
#include <cstdio>
#include <iostream>
using namespace std;

typedef long long ll;

const int MAXM = 25;          // m 不超过 20，留一点余量
const int MAXN = 25;          // n 不超过 20，留一点余量

int n, m, x, y;
ll f[MAXN][MAXM];             // f[i][j] 表示从 (0,0) 走到 (i,j) 的合法路径数
bool blocked[MAXN][MAXM];     // blocked[i][j] 为 true 表示 (i,j) 是马的控制点

// 8 个马跳跃的日字方向（dx,dy）
const int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
const int dy[8] = {-1, -2, -2, -1, 1, 2, 2, 1};

// 判断坐标 (i,j) 是否在棋盘内
inline bool in_board(int i, int j) {
    return i >= 0 && i <= n && j >= 0 && j <= m;
}

// 标记马的控制点：马自身 + 8 个日字跳跃点
void mark_control() {
    // 马自身
    blocked[x][y] = true;
    // 8 个日字方向
    for (int k = 0; k < 8; k++) {
        int ni = x + dx[k];
        int nj = y + dy[k];
        if (in_board(ni, nj)) {
            blocked[ni][nj] = true;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> x >> y;

    mark_control();

    // 起点保证不是控制点，初始化为 1
    f[0][0] = 1;

    // 按行从上到下、按列从左到右递推
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (blocked[i][j]) {
                f[i][j] = 0;  // 控制点不可达
                continue;
            }
            if (i > 0) f[i][j] += f[i - 1][j];  // 从上方走下来
            if (j > 0) f[i][j] += f[i][j - 1];  // 从左方走过来
        }
    }

    cout << f[n][m] << "\n";
    return 0;
}

【例3.6】过河卒(Noip2002)

目录

题目描述

思路

参考代码