泽君代码找虫

吴老师

2026-07-23 14:59:24

发布于：广东

13阅读

0回复

0点赞

这份代码还有 3 个关键问题。

1. 没有更新距离，也没有把新位置加入队列

你在枚举 nx 后，只进行了判断：

if(nx<1||nx>n) continue;
if(dis[nx]) continue;

但是后面没有写：

dis[nx] = dis[x] + 1;
q.push(nx);

所以队列中始终只有起点 a，程序只会搜索一层。

2. 判断是否到达终点写错了

你写的是：

if(dis[nx] == b)

dis[nx] 表示到达 nx 的最少跳跃次数，而 b 是目标石板编号，两者不能比较。

应该判断：

if(nx == b)

然后输出距离：

cout << dis[x] + 1;

3. 起点没有标记为访问过

全局数组 dis 初始值为 0，你使用：

if(dis[nx]) continue;

判断是否访问过。

但起点 a 的 dis[a] 也是 0，所以之后可能重新跳回起点，再次进入队列。

可以让：

dis[a] = 1;

这里把 dis 当作“实际距离加一”，最后输出时减一。

不过更推荐把 dis 全部初始化为 -1。

推荐修改版

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

const int N = 210;

int n, a, b;
int k[N];
int dis[N];

int main() {
    cin >> n >> a >> b;

    for(int i = 1; i <= n; i++) {
        cin >> k[i];
    }

    memset(dis, -1, sizeof(dis));

    queue<int> q;
    q.push(a);
    dis[a] = 0;

    while(!q.empty()) {
        int x = q.front();
        q.pop();

        int dx[] = {x - k[x], x + k[x]};

        for(int nx : dx) {
            // 跳出石板范围
            if(nx < 1 || nx > n) {
                continue;
            }

            // 已经访问过
            if(dis[nx] != -1) {
                continue;
            }

            dis[nx] = dis[x] + 1;
            q.push(nx);

            // 到达目标
            if(nx == b) {
                cout << dis[nx];
                return 0;
            }
        }
    }

    cout << -1;

    return 0;
}

实际上不需要单独判断 a == b，因为也可以统一写成 BFS 结束后输出：

cout << dis[b];

还可以进一步简化为：

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

int main() {
    int n, a, b;
    cin >> n >> a >> b;

    vector<int> k(n + 1);
    vector<int> dis(n + 1, -1);

    for(int i = 1; i <= n; i++) {
        cin >> k[i];
    }

    queue<int> q;
    q.push(a);
    dis[a] = 0;

    while(!q.empty()) {
        int x = q.front();
        q.pop();

        int nxt[] = {x - k[x], x + k[x]};

        for(int nx : nxt) {
            if(nx < 1 || nx > n) continue;
            if(dis[nx] != -1) continue;

            dis[nx] = dis[x] + 1;
            q.push(nx);
        }
    }

    cout << dis[b];

    return 0;
}