1 条题解

  • 0
    @ 2025-6-11 19:54:47
    #include <bits/stdc++.h>
    using namespace std;
    const int MAXN = 200;
    queue<int> q;       // 存还需要搜索的点
    bool vis[MAXN + 5]; // vis[i] 存 i 这个点搜过了没有
    int dis[MAXN + 5];  // dis[i] 存从起点几步能走到 i
    int n, a, b;        // 楼层(点的个数)、起点终点
    int k[MAXN + 5];    // 第 i 层能走到 i+k[i], i-k[i]
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin >> n >> a >> b;
        for (int i = 1; i <= n; i++)
            cin >> k[i];
        // 起点入队
        vis[a] = true;
        dis[a] = 0;
        q.push(a);
        // 队列非空且没到终点就继续搜
        while (!q.empty() && !vis[b])
        {
            // 取出队头
            int now = q.front();
            q.pop();
            // 考虑 now 能走到哪儿
            int nxt; // 下一步到的位置 next
            // now-k[now],能走到,且没走过
            nxt = now - k[now];
            if (1 <= nxt && nxt <= n && !vis[nxt])
            {
                vis[nxt] = true;
                dis[nxt] = dis[now] + 1;
                q.push(nxt);
            }
            // now+k[now],能走到,且没走过
            nxt = now + k[now];
            if (1 <= nxt && nxt <= n && !vis[nxt])
            {
                vis[nxt] = true;
                dis[nxt] = dis[now] + 1;
                q.push(nxt);
            }
        }
        if (!vis[b])
            cout << -1;
        else
            cout << dis[b];
        return 0;
    }
    
    • 1

    信息

    ID
    579
    时间
    1000ms
    内存
    128MiB
    难度
    4
    标签
    (无)
    递交数
    22
    已通过
    16
    上传者