马的遍历

形式化题目

有一个 $n \times m$ 的棋盘和起点 $(x, y)$ 。马按"日字"走，一次跳跃恰有 8 种可能落点。求从起点到棋盘上每个格子的最少步数，不可达的格子记为 $-1$ ，输出完整的 $n \times 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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88/**
 * 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-13 13:19
 * update_at: 2026-08-13 13:20
 */
// brute.cpp：小数据暴力解，对每个终点单独跑一次 BFS，用来理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 35; // 暴力解只适合小棋盘

int n, m, sx, sy;
int ans[MAXN][MAXN]; // ans[i][j]：起点到 (i,j) 的最少步数
int dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
int dy[8] = {-1, 1, -2, 2, -2, 2, -1, 1};

struct Node {
    int x;
    int y;
};

bool in_board(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= m;
}

// 朴素做法：从起点单独跑一次 BFS，只求到达 (tx, ty) 的最少步数。
int single_bfs(int tx, int ty) {
    static int dista[MAXN][MAXN];
    memset(dista, -1, sizeof(dista));

    queue<Node> q;
    dista[sx][sy] = 0;
    q.push((Node){sx, sy});

    while (!q.empty()) {
        Node u = q.front();
        q.pop();

        if (u.x == tx && u.y == ty) {
            return dista[tx][ty];
        }

        for (int i = 0; i < 8; i++) {
            int nx = u.x + dx[i];
            int ny = u.y + dy[i];

            if (!in_board(nx, ny)) {
                continue;
            }
            if (dista[nx][ny] != -1) {
                continue;
            }

            dista[nx][ny] = dista[u.x][u.y] + 1;
            q.push((Node){nx, ny});
        }
    }

    return -1; // 不可达
}

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

    cin >> n >> m >> sx >> sy;

    // 对每个格子都单独求一次，总复杂度 O((nm)^2)，只适合小数据。
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            ans[i][j] = single_bfs(i, j);
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (j > 1) {
                cout << ' ';
            }
            cout << ans[i][j];
        }
        cout << '\n';
    }

    return 0;
}

brute.cpp 对每个终点格子单独从起点跑一次 BFS：求一个格子的答案就要遍历一次棋盘，而终点有 $nm$ 个，总复杂度 $O((nm)^2)$ ，在 $400 \times 400$ 的棋盘上不可行。但它的重复劳动暴露了关键点——起点始终只有一个，终点却有 $nm$ 个，为什么不让一次搜索同时解决所有终点？

关键观察：马每一步的代价都是 $1$ ，把每个格子看成点、一次合法跳跃看成一条边权为 $1$ 的边后，题目就是标准的无权图单源最短路。无权图不需要 Dijkstra，BFS 按层扩展——第 $k$ 层恰好是所有距离起点 $k$ 步的格子——因此每个格子第一次被访问时记录的距离就一定是最短步数。

以样例 $3 \times 3$ 、起点 $(1,1)$ 为例，BFS 的扩展过程如下：

步数	该层到达的格子	距离
0	(1,1)	0
1	(2,3)、(3,2)	1
2	(3,1)、(1,3)	2
3	(1,2)、(2,1)	3
4	(3,3)	4
未访问	(2,2)	-1

观察每一行：第 $k$ 层的格子只能由第 $k-1$ 层的格子跳一步到达，BFS 保证每个格子第一次出现就落在它的最短层。例如 $(3,3)$ 同样可以被更长的绕路到达，但它第一次出现是在第 4 层，答案就记为 4； $(2,2)$ 永远不被访问（马步每次改变格子坐标和的奇偶性， $3 \times 3$ 里它不可达），保持 $-1$ 。

正式做法：

距离数组全部初始化为 $-1$ ，同时充当"未访问"标记；
起点距离设为 $0$ 并入队；
每次取出队首格子，枚举 8 个马步方向，把棋盘内且未访问的邻居距离设为当前距离加 $1$ 并入队。

注意不需要真的建图：8 个邻居由 dx[] / dy[] 方向数组在出队时现场计算，这是一张"隐式图"，省掉了存边。

代码

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
70
71
72
73
74
75
76/**
 * 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-13 13:19
 * update_at: 2026-08-13 13:20
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 405; // n, m <= 400

int n, m, sx, sy;
int dista[MAXN][MAXN];          // dista[i][j]：起点到 (i,j) 的最少步数，-1 表示未访问/不可达
int dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2}; // 马的 8 种跳法
int dy[8] = {-1, 1, -2, 2, -2, 2, -1, 1};

struct Node {
    int x;
    int y;
};

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

// 从起点做一次 BFS，求出到所有格子的最短步数。
void bfs() {
    queue<Node> q;
    dista[sx][sy] = 0;
    q.push((Node){sx, sy});

    while (!q.empty()) {
        Node u = q.front();
        q.pop();

        for (int i = 0; i < 8; i++) {
            int nx = u.x + dx[i];
            int ny = u.y + dy[i];

            if (!in_board(nx, ny)) {
                continue;
            }
            if (dista[nx][ny] != -1) {
                continue;
            }

            // 第一次访问到的步数一定最短，直接记录并入队。
            dista[nx][ny] = dista[u.x][u.y] + 1;
            q.push((Node){nx, ny});
        }
    }
}

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

    cin >> n >> m >> sx >> sy;

    memset(dista, -1, sizeof(dista)); // -1 同时表示未访问和不可达
    bfs();

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (j > 1) {
                cout << ' ';
            }
            cout << dista[i][j];
        }
        cout << '\n';
    }

    return 0;
}

复杂度

时间：每个格子最多入队一次，每次出队检查 8 个方向， $O(nm)$ 。
空间：距离数组加队列， $O(nm)$ 。

总结

"每次走一步求最少步数"是典型的无权图最短路信号：先问状态是什么（格子）、一步怎么转移（8 个马步）、转移是否等代价（都是 1），三个问题回答清楚后，单源 BFS 就是标准答案。本题还展示了隐式图的好处：棋盘上动态生成邻居，省去建图。rbook 的《图的遍历》讲解了 DFS / BFS 遍历的基础框架，本解的队列层扩展正是其中的 BFS 路线。

图示解析

这张 ASCII 图展示整道题的解题路线：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20朴素做法（brute.cpp）
  对每个终点 (i,j) 单独从起点跑一次 BFS    O(nm) 每次
        |
        | 瓶颈：终点有 n*m 个，总复杂度 O((n*m)^2) 太大
        | 重复劳动：所有 BFS 都从同一个起点出发
        v
关键观察
  马步代价都是 1 -> 无权图
  边权全相等 -> 最短路不需要 Dijkstra
  BFS 按层扩展，第 k 层 = 距离 k 步的格子
        |
        v
单源 BFS（main.cpp）
  dista[][] 初始 -1（兼作未访问标记）
  起点距离 0 入队
  出队 -> 8 个马步方向现场生成邻居（隐式图）
  首次访问即最短，记录 dista = dista[u] + 1 并入队
        |
        v
复杂度 O(n*m)，空间 O(n*m)

图中三条主线对应"暴力慢在哪"“观察到什么性质”“正式解如何利用它”。核心是把 $nm$ 次重复搜索合并成一次按层扩展：BFS 的层序号本身就是最短步数，所以"第一次访问"不需要额外证明最短性，队列结构天然保证了这一点。

目录

形式化题目

思路

代码

复杂度

总结

图示解析