机器人复健指南

形式化题目

在 $n \times n$ 的网格中从 $(x,y)$ 出发，每次可以向八个方向之一移动（位移为 $(\pm1,\pm2)$ 或 $(\pm2,\pm1)$ ，即马步），不能走出网格。求不超过 $k$ 步能到达的格子总数（含起点）。

思路

每个格子是图上的一个节点，八种马步是节点之间的边。从起点做 BFS 求最短步数，统计步数不超过 $k$ 的格子即可。

为什么 BFS

马步移动每次代价相同，BFS 先入队的路径一定最短，所以每个格子第一次被访问时就记录到了最少步数。步数达到 $k$ 的格子不再扩展。

边界处理

跳出的方向通过范围检查排除；已访问的格子用 distance != -1 判重，避免重复入队。由于 $n,k \le 100$ ，图最多 $10^4$ 个节点，BFS 完全可行。

代码

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-07-31 16:21
 * update_at: 2026-08-17 22:53
 */
#include <bits/stdc++.h>
using namespace std;

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

    int n, k, x, y;
    cin >> n >> k >> x >> y;

    // distance[i][j] 表示起点到 (i,j) 的最少步数，-1 表示未访问
    int distance[105][105];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) distance[i][j] = -1;
    }

    // 八种马步位移
    int dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
    int dy[8] = {-1, 1, -2, 2, -2, 2, -1, 1};

    // BFS 逐层扩展，先到达的步数一定最小
    queue<pair<int, int> > que;
    distance[x][y] = 0;
    que.push(make_pair(x, y));
    while (!que.empty()) {
        pair<int, int> current = que.front();
        que.pop();
        if (distance[current.first][current.second] == k) continue;

        for (int direction = 0; direction < 8; direction++) {
            int next_x = current.first + dx[direction];
            int next_y = current.second + dy[direction];
            if (next_x < 1 || next_x > n || next_y < 1 || next_y > n) continue;
            if (distance[next_x][next_y] != -1) continue;
            distance[next_x][next_y] = distance[current.first][current.second] + 1;
            que.push(make_pair(next_x, next_y));
        }
    }

    // 统计所有步数不超过 k 的方格
    long long answer = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (distance[i][j] != -1 && distance[i][j] <= k) answer++;
        }
    }
    cout << answer << '\n';
    return 0;
}

复杂度

图有 $n^2$ 个节点，每个节点检查 8 条边，时间与空间复杂度均为 $O(n^2)$ 。

总结

本题是标准图 BFS，难点只在把八方向位移和边界条件写对。把位移写成两个数组 dx/dy 统一枚举，既简洁又不容易漏方向。

目录

形式化题目

思路

为什么 BFS

边界处理

代码

复杂度

总结