大家好，今天我们来看CSP202506B. 机器人复健指南这道题目

题目要求的是k步内可以到达的方格总数，是一道很经典的搜索题目。

CCF-CSP中，搜索的常见算法无非两种：BFS,DFS

而BFS按层扩展，每一步向外扩散一圈，天然匹配"k步内"的统计需求，而且无需处理递归深度和回溯，实现简单，所以这道题我们用BFS来解决

在执行BFS的过程中，我们需要队列来记录当前层次的节点，通过这些节点来找到下一步可行的节点。

伪代码如下：

1. 初始化队列，将起点 (x,y) 入队，步数记为0，visited[x][y]=true
2. 初始化答案计数 ans = 1（包含起点）
3. while 队列不为空:
     a. 弹出队首节点 (cx, cy, step)
     b. 如果 step == k，跳过扩展（不再深入）
     c. 否则，遍历8个方向：
        1 计算新坐标 (nx, ny) = (cx + dx[i], cy + dy[i])
        2 判断是否在边界内 (1≤nx≤n, 1≤ny≤n) 且未访问
        3 若合法，标记visited，入队 (nx, ny, step+1)，ans++
4. 输出 ans

在实际编码中，我们可以把边界判断和访问检查封装成一个 check 函数，让代码更清晰易读。这样我们就得到了如下代码：

 # include <bits/stdc++.h>

using namespace std;

#define itn int
#define ll long long
#define ld long double
#define mod 998244353

int dx[]={-2,-2,-1,-1,1,1,2,2};                                       // 横向移动
int dy[]={-1,1,-2,2,2,-2,1,-1};                                       // 纵向移动
const int N=110;
bool vis[N][N];                                                       // 标记是否访问过
typedef struct step {
    int x,y,times;
}step;
int n,k;
bool check(step &s) {
    return s.x>=1&&s.x<=n&&s.y>=1&&s.y<=n&&!vis[s.x][s.y]&&s.times<=k;// 判断：在边界内、未访问、步数不超过k
}
void bfs(int sx,int sy) {
    queue<step> q;                                                    // 维护队列
    step Step;
    Step.x=sx;Step.y=sy;
    Step.times=0;
    q.push(Step);
    vis[sx][sy]=true;                                                 // 对合法坐标做标记
    while(!q.empty()) {
        Step=q.front();
        q.pop();
        for(int i=0;i<8;i++) {
            int nx=Step.x+dx[i];
            int ny=Step.y+dy[i];
            step newStep;
            newStep.x=nx;newStep.y=ny;
            newStep.times=Step.times+1;
            if(check(newStep)) {
                q.push(newStep);
                vis[newStep.x][newStep.y]=true;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>n>>k;
    int sx,sy;
    cin>>sx>>sy;
    bfs(sx,sy);
    int ans=0;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            if(vis[i][j]) ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

时间复杂度：O(n²)，每个格子最多入队一次，每次扩展检查8个方向

以上就是本题的 BFS 解法。感谢阅读，欢迎评论区留言讨论！

转载标明出处