[NOIP2002-普及] 过河卒

题目描述

棋盘上 $A(0,0)$ 有一个卒，要走到 $B(n,m)$ （ $0 \leqslant n,m \leqslant 20$ ），每步只能向下或向右。棋盘上有对方的马 $C(h_x,h_y)$ ，马所在点及它按“马走日”跳一步能到的点都是控制点。求卒从 $A$ 到 $B$ 不经过任何控制点的路径条数。结果可能很大。

思路

标记马和马脚共 9 个控制点。设 $f(i,j)$ 为到 $(i,j)$ 的路径数，若 $(i,j)$ 是控制点则 $f(i,j)=0$ ，否则 $f(i,j)=f(i-1,j)+f(i,j-1)$ 。用一维滚动数组自上而下、自左而右递推，答案为 $f(n,m)$ 。

参考代码

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#!/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-10-02 04:52
# update_at: 2026-10-02 04:52

import sys

# 马的 8 个跳跃位移（“马走日”）
JUMPS = ((1, 2), (2, 1), (-1, 2), (-2, 1), (1, -2), (2, -1), (-1, -2), (-2, -1))


def solve() -> None:
    n, m, hx, hy = map(int, sys.stdin.buffer.read().split())

    # 马的控制点 = 马所在点 + 8 个跳跃落点；棋盘外的点不会被查到，留在集合里无害
    blocked = {(hx, hy)} | {(hx + dx, hy + dy) for dx, dy in JUMPS}

    # 滚动数组：f[j] = 从 (0,0) 走到“当前行”第 j 列的路径数
    f: list[int] = [0] * (m + 1)
    f[0] = 0 if (0, 0) in blocked else 1
    for i in range(n + 1):
        for j in range(m + 1):
            if (i, j) in blocked:
                f[j] = 0          # 控制点不可通行，路径数清零
            elif j:
                f[j] += f[j - 1]  # f[j] 原值是“从上面来”，f[j-1] 是“从左边来”
    print(f[m])


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/**
 * 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-06 12:40
 * update_at: 2026-10-06 12:40
 */

#include <iostream>
using namespace std;

typedef long long ll;

const int MAXM = 25;        // 列数上限

ll f[MAXM];                 // 滚动数组：当前行到第 j 列的路径数
bool blocked[MAXM][MAXM];   // 马的控制点标记

// 马的 8 个跳跃位移（“马走日”）
const int dx[8] = {1, 2, -1, -2, 1, 2, -1, -2};
const int dy[8] = {2, 1, 2, 1, -2, -1, -2, -1};

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

    ll n, m, hx, hy;
    cin >> n >> m >> hx >> hy;

    // 标记马所在点及 8 个跳跃落点
    blocked[hx][hy] = true;
    for (int k = 0; k < 8; k++) {
        ll nx = hx + dx[k];
        ll ny = hy + dy[k];
        if (0 <= nx && nx <= n && 0 <= ny && ny <= m) {
            blocked[nx][ny] = true;
        }
    }

    // 起点被控制则答案自然为 0
    f[0] = blocked[0][0] ? 0 : 1;

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (blocked[i][j]) {
                f[j] = 0;           // 控制点不可通行
            } else if (j > 0) {
                f[j] += f[j - 1];   // 上面来 + 左边来
            }
            // j == 0 且非控制点时保留上一行传下来的 f[0]
        }
    }

    cout << f[m] << endl;
    return 0;
}

[NOIP2002-普及] 过河卒

目录

题目描述

思路

参考代码