AcWing 1100. 抓住那头牛【 BFS广度优先搜索】题解

布满荆棘的人生 2021-07-25 02:40 313阅读 0赞

### 目录 ###

*   *   *  1.题目
         *  2.思路
         *  3.代码

### 1.题目 ###

农夫知道一头牛的位置，想要抓住它。

农夫和牛都位于数轴上，农夫起始位于点 N，牛位于点 K。

农夫有两种移动方式：

从 X 移动到 X−1 或 X+1，每次移动花费一分钟  
从 X 移动到 2∗X，每次移动花费一分钟  
假设牛没有意识到农夫的行动，站在原地不动。

农夫最少要花多少时间才能抓住牛？

**输入格式**  
共一行，包含两个整数N和K。

**输出格式**  
输出一个整数，表示抓到牛所花费的最少时间。

**数据范围**  
0≤N,K≤105  
**输入样例：**  
5 17  
**输出样例：**  
4

### 2.思路 ###

题目讲述一共有3种移动情况且权重一致

从 X 移动到 X−1

从 X 移动到 X+1

从 X 移动到 2∗X

相当于X 与X - 1,X + 1,2 \* X ,各连一条边,从n开始进行bfs到k，dist\[k\]表示k点到n点的最短距离

### 3.代码 ###

#include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    
    const int N=2e5+10;
    int dist[N], q[N];
    int n,k;
    int bfs()
    { 
        memset(dist,-1,sizeof dist);
        int hh=0,tt=0;
        q[0]=n;
        dist[n]=0;
        while(hh<=tt)
        { 
            int t=q[hh++];
            if(t==k) return dist[k];
            if(t+1<N&&dist[t+1]==-1)
            { 
                dist[t+1]=dist[t]+1;
                q[++tt]=t+1;
            }
            if(t-1>=0&&dist[t-1]==-1)
            { 
                dist[t-1]=dist[t]+1;
                q[++tt]=t-1;
            }
            if(t*2<N&&dist[t*2]==-1)
            { 
                dist[t*2]=dist[t]+1;
                q[++tt]=t*2;
            }
        }
        return -1;
    }
    int main()
    { 
        cin>>n>>k;
        cout<<bfs()<<endl;
        return 0;
    }