1 条题解

  • 0
    @ 2026-2-17 22:10:09
    #include<bits/stdc++.h>
    using namespace std;
    
    // 最大搜索范围:M最大为1e5,2*M足够覆盖所有有效搜索
    const int MAX = 2e5 + 10;
    // dist[x]:从起点N到位置x的最少步数
    int dist[MAX];
    
    int main()
    {
        // 关闭cin同步,加速输入
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    
        int N, M;
        // [1] 读取鸡的位置N、狗的位置M
        cin >> N >> M;
    
        // [2] 特殊情况:鸡在狗的右侧/同一位置,直接向左走即可
        if(N >= M)
        {
            cout << N - M << endl;
            return 0;
        }
    
        // [3] 初始化距离数组,-1表示该位置未被访问
        memset(dist, -1, sizeof(dist));
        queue<int> q; // BFS队列,存储待遍历的位置
    
        // [4] 起点初始化:N的步数为0,入队启动BFS
        dist[N] = 0;
        q.push(N);
    
        // [5] BFS核心循环,层级遍历所有可达位置
        while(!q.empty())
        {
            // 取出队首的当前位置
            int x = q.front();
            q.pop();
    
            // 遍历3种合法操作,生成下一步的位置
            // 操作1:向右走一步
            int nx = x + 1;
            // 合法性检查:位置在有效范围内,且未被访问过
            if(nx <= 2*M && dist[nx] == -1)
            {
                dist[nx] = dist[x] + 1;
                if(nx == M) // 到达终点,直接输出结果
                {
                    cout << dist[nx] << endl;
                    return 0;
                }
                q.push(nx); // 新位置入队
            }
    
            // 操作2:向左走一步
            nx = x - 1;
            if(nx >= 0 && dist[nx] == -1)
            {
                dist[nx] = dist[x] + 1;
                if(nx == M)
                {
                    cout << dist[nx] << endl;
                    return 0;
                }
                q.push(nx);
            }
    
            // 操作3:飞到2倍位置
            nx = x * 2;
            if(nx <= 2*M && dist[nx] == -1)
            {
                dist[nx] = dist[x] + 1;
                if(nx == M)
                {
                    cout << dist[nx] << endl;
                    return 0;
                }
                q.push(nx);
            }
        }
    
        return 0;
    }
    
    • 1

    信息

    ID
    1306
    时间
    1000ms
    内存
    256MiB
    难度
    1
    标签
    递交数
    1
    已通过
    1
    上传者