1 条题解

  • 0
    @ 2025-6-4 19:37:15
        // 起点入队
        // 队列非空且没到终点就继续搜
            // 取出队头
            // 考虑 now 能走到哪儿
            // now-1,能走到,且没走过
            // now+1,能走到,且没走过
            // now*2,能走到,且没走过
    

    #include <bits/stdc++.h>
    using namespace std;
    const int MAXN = 200000;
    queue<int> q;       // 存还需要搜索的点
    bool vis[MAXN + 5]; // vis[i] 存 i 这个点搜过了没有
    int dis[MAXN + 5];  // dis[i] 存从起点几步能走到 i
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        int n, k; // 人的起点,牛的位置
        cin >> n >> k;
        // 起点入队
        q.push(n);
        vis[n] = true;
        dis[n] = 0;
        // 队列非空且没到终点就继续搜
        while (!q.empty() && !vis[k])
        {
            // 取出队头
            int now = q.front();
            q.pop();
            // 考虑 now 能走到哪儿
            // now-1,能走到,且没走过
            if (0 <= now - 1 && now - 1 <= MAXN && vis[now - 1] == false)
            {
                vis[now - 1] = true;
                dis[now - 1] = dis[now] + 1;
                q.push(now - 1);
            }
            // now+1,能走到,且没走过
            if (0 <= now + 1 && now + 1 <= MAXN && vis[now + 1] == false)
            {
                vis[now + 1] = true;
                dis[now + 1] = dis[now] + 1;
                q.push(now + 1);
            }
            // now*2,能走到,且没走过
            if (0 <= now * 2 && now * 2 <= MAXN && vis[now * 2] == false)
            {
                vis[now * 2] = true;
                dis[now * 2] = dis[now] + 1;
                q.push(now * 2);
            }
        }
        cout << dis[k];
        return 0;
    }
    
    • 1

    信息

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