AcWing 1100. 抓住那头牛

谁借莪１个温暖的怀抱￠ 2024-04-08 13:17 81阅读 0赞

## AcWing 1100. 抓住那头牛 ##

### 原题链接 ###

[AcWing 1100. 抓住那头牛][AcWing 1100.]

### 算法标签 ###

BFS

### 思路 ###

BFS可以求解对于边权为1图的最短路

移动过程中，移动至最短路所经过的点的合法范围  
若从  X X X 移动到  X + 1 X+1 X\+1  
说明移动前位于牛的前方 则移动后到达牛的位置或依旧位于牛的前方 即X+1<=K  
若从  X X X 移动到  X ∗ 2 X\*2 X∗2  
说明移动前位于牛的前方 则移动后到达牛的位置或依旧位于牛的前方 即X+2<=K  
若 从  X X X 移动到  X − 1 X−1 X−1  
情况1  
移动前位于牛的后方 则移动后到达牛的位置或依旧位于牛的后方 即X-1>=K  
情况2  
为方便从  X X X 移动到  X ∗ 2 X\*2 X∗2  
移动前位于牛的前方 则移动后依旧位于牛的前方 即X-1<K

### 我的代码 ###

#include<bits/stdc++.h>
    #define int long long
    #define rep(i, a, b) for(int i=a;i<b;++i)
    #define Rep(i, a, b) for(int i=a;i>b;--i)
    #define x first
    #define y second
    using namespace std;
    typedef pair<int, int> PII;
    const int N = 100005;
    int d[N];
    int q[N];
    int n, k;
    inline int read(){
       int s=0,w=1;
       char ch=getchar();
       while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
       while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
       return s*w;
    }
    void put(int x) {
        if(x<0) putchar('-'),x=-x;
        if(x>=10) put(x/10);
        putchar(x%10^48);
    }
    int bfs(){
        int hh=0, tt=0;
        memset(d, -1, sizeof d);
        q[0]=n;
        d[n]=0;
        while(hh<=tt){
            int t=q[hh++];
            if(t==k){
                return d[k];
            }
            if(t+1<=k&&d[t+1]==-1){
                d[t+1]=d[t]+1;
                q[++tt]=t+1;
            }
            if(t-1>=k&&d[t-1]==-1){
                d[t-1]=d[t]+1;
                q[++tt]=t-1;
            }
            if(t-1<k&&d[t-1]==-1){
                d[t-1]=d[t]+1;
                q[++tt]=t-1;
            }
            if(t*2<=k*2&&d[t*2]==-1){
                d[t*2]=d[t]+1;
                q[++tt]=t*2;
            }
        }
    }
    signed main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        n=read(), k=read();
        printf("%lld", bfs());
        return 0;
    }

y总代码  
可以不进行细致分析 得出可能范围即可

#include<bits/stdc++.h>
    #define int long long
    #define rep(i, a, b) for(int i=a;i<b;++i)
    #define Rep(i, a, b) for(int i=a;i>b;--i)
    #define x first
    #define y second
    using namespace std;
    typedef pair<int, int> PII;
    const int N = 200005;
    int d[N];
    int q[N];
    int n, k;
    inline int read(){
       int s=0,w=1;
       char ch=getchar();
       while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
       while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
       return s*w;
    }
    void put(int x) {
        if(x<0) putchar('-'),x=-x;
        if(x>=10) put(x/10);
        putchar(x%10^48);
    }
    int bfs(){
        int hh=0, tt=0;
        memset(d, -1, sizeof d);
        // 起始点入队
        q[0]=n;
        // 起始点距离为零
        d[n]=0;
        while(hh<=tt){
            int t=q[hh++];
            // 抓住位于点 K的牛
            if(t==k){
                return d[k];
            }
            // 若向后移动后位于范围内且尚未走过 
            if(t+1<N&&d[t+1]==-1){
                d[t+1]=d[t]+1;
                q[++tt]=t+1;
            }
            // 若向前移动后位于范围内且尚未走过
            if(t-1>=0&&d[t-1]==-1){
                d[t-1]=d[t]+1;
                q[++tt]=t-1;
            }
            // 若移动至t*2位于范围内且尚未走过
            if(t*2<=N&&d[t*2]==-1){
                d[t*2]=d[t]+1;
                q[++tt]=t*2;
            }
        }
    }
    signed main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        n=read(), k=read();
        printf("%lld", bfs());
        return 0;
    }

参考文献  
[AcWing 1100. 抓住那头牛y总代码][AcWing 1100. _y]  
[AcWing 1100. 抓住那头牛y总视频讲解][AcWing 1100. _y 1]

原创不易  
转载请标明出处  
如果对你有所帮助 别忘啦点赞支持哈  
![在这里插入图片描述][9cb4cb80a18345158f8a69e2f196e5b9.png]

[AcWing 1100.]: https://www.acwing.com/problem/content/1102/
[AcWing 1100. _y]: https://www.acwing.com/activity/content/code/content/130865/
[AcWing 1100. _y 1]: https://www.acwing.com/problem/content/video/1102/
[9cb4cb80a18345158f8a69e2f196e5b9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/93c1c0281e8843bbadc03aff38032d15.png