[NOIP 2002 普及组] 过河卒

题意

卒从 (0,0) 走到 (n,m)，每次只能向右或向下。棋盘上有一匹马，马所在格和马一步能跳到的格子都不能经过。

求从起点到终点的合法路径数。

思路

先标记所有不能走的格子：

马所在位置；
马按日字跳能到达的 8 个位置。

然后做网格 DP。令 dp[x][y] 表示从 (0,0) 走到 (x,y) 的路径数。

如果 (x,y) 被马控制：

text

1dp[x][y] = 0

否则卒只能从上方或左方走来：

text

1dp[x][y] = dp[x-1][y] + dp[x][y-1]

不存在的来源按 0 处理，起点 dp[0][0] = 1。

样例 DP 表格

样例中 B=(6,6)，马在 (3,3)，x 表示控制点：

x\y	0	1	2	3	4	5	6
0	1	1	1	1	1	1	1
1	1	2	x	1	x	1	2
2	1	x	0	1	1	x	2
3	1	1	1	x	1	1	3
4	1	x	1	1	2	x	3
5	1	1	x	1	x	0	3
6	1	2	2	3	3	3	6

最终 dp[6][6] = 6。

Python 知识

二维数组要用 [[0] * (m + 1) for _ in range(n + 1)]，不要写成浅拷贝形式。
马的 9 个控制偏移可以放在列表里统一枚举。
Python 大整数自动扩展，路径数不需要手写高精度。

参考笔记：

/home/rainboy/mycode/hugo-blog/content/program_language/python/cpp_to_python_pitfalls.md
/home/rainboy/mycode/hugo-blog/content/program_language/python/math_tools.md

代码

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
36n, m, horse_x, horse_y = map(int, input().split())

blocked = [[False] * (m + 1) for _ in range(n + 1)]

for dx, dy in [
    (0, 0),
    (1, 2),
    (2, 1),
    (2, -1),
    (1, -2),
    (-1, -2),
    (-2, -1),
    (-2, 1),
    (-1, 2),
]:
    x = horse_x + dx
    y = horse_y + dy
    if 0 <= x <= n and 0 <= y <= m:
        blocked[x][y] = True

dp = [[0] * (m + 1) for _ in range(n + 1)]
dp[0][0] = 1

for x in range(n + 1):
    for y in range(m + 1):
        if blocked[x][y]:
            dp[x][y] = 0
            continue
        if x == 0 and y == 0:
            continue
        if x > 0:
            dp[x][y] += dp[x - 1][y]
        if y > 0:
            dp[x][y] += dp[x][y - 1]

print(dp[n][m])

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/**
 * 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-08-04 12:24
 * update_at: 2026-08-04 12:24
 */

/* P1002 [NOIP 2002 普及组] 过河卒 */
/* 网格路径计数 DP：卒只能向右/向下走，马所在格与马一步能跳到的格子不能走。
 * 每个格子的路径数 = 上方格子的路径数 + 左方格子的路径数。 */

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAXN = 25;

int n, m;             // 终点坐标 (n, m)，起点 (0, 0)
int hx, hy;           // 马的位置
ll dp[MAXN][MAXN];    // dp[x][y]：从 (0,0) 走到 (x,y) 的合法路径数
bool blocked[MAXN][MAXN]; // blocked[x][y] = true 表示该格不能走

// 马的控制格偏移：0 号是马自己，其余 8 个是马一步能跳到的位置
int dx[] = {0, 1, 1, -1, -1, 2, 2, -2, -2};
int dy[] = {0, 2, -2, 2, -2, 1, -1, 1, -1};

// 判断 (x, y) 是否在棋盘内
bool in_board(int x, int y) {
    return x >= 0 && x <= n && y >= 0 && y <= m;
}

// 把马所在格和 8 个控制格全部标记为不能走
void mark_horse() {
    for (int i = 0; i < 9; i++) {
        int nx = hx + dx[i];
        int ny = hy + dy[i];
        if (in_board(nx, ny)) {
            blocked[nx][ny] = true;
        }
    }
}

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

    cin >> n >> m >> hx >> hy;
    mark_horse();

    // 起点本身不能被马控制
    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]) {
                dp[i][j] = 0;   // 不能走的格子路径数为 0
                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] << '\n';
    return 0;
}

复杂度

标记控制点是 $O(1)$ ，DP 遍历整个棋盘是 $O(nm)$ 。空间复杂度为 $O(nm)$ 。

总结

只向右和向下走，说明每个格子只依赖上方和左方；把不能走的格子强制为 0，就是完整的网格路径计数 DP。

一图流解析

这张图可以作为读完正文后的复盘。

[NOIP 2002 普及组] 过河卒

目录

题意

思路

样例 DP 表格

Python 知识

代码

复杂度

总结

一图流解析