题目描述

农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点N(0≤N≤100000)，牛位于点K(0≤K≤100000)。农夫有两种移动方式：

1、从X移动到X−1或X+1，每次移动花费一分钟

2、从X移动到2×X，每次移动花费一分钟

假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？

【输入】
两个整数，N和K。

【输出】
一个整数，农夫抓到牛所要花费的最小分钟数。

样例

【输入样例】
5 17
【输出样例】
4

这道题是典型的bfs例题，需要用到队列（先进先出），结构体，然后用一个while循环就可以了

C++ 代码

#include<bits/stdc++.h>
using namespace std;
struct node{
    int data;
    int step;
};
const int N=100010;
bool vis[N];
queue<node> a;
int main(){
    int n,m;
    cin>>n>>m;
    node start;
    start.data=n;
    start.step=0;
    a.push(start);
    vis[n]=true;
    while(!a.empty())
    {
        node cmp;
        cmp=a.front();
        if(cmp.data==m)
        {
            cout << cmp.step << endl;
            return 0;
        }
            node tmp;
            if(cmp.data-1>=0 && !vis[cmp.data-1])
            {
                tmp.data=cmp.data-1;
                tmp.step=cmp.step+1;
                a.push(tmp);
                vis[tmp.data]=true;
            }
            if(cmp.data+1<=N && !vis[cmp.data+1])
            {
                tmp.data=cmp.data+1;
                tmp.step=cmp.step+1;
                a.push(tmp);
                vis[tmp.data]=true;
            }
            if(cmp.data*2<=N && !vis[cmp.data*2])
            {
                tmp.data=cmp.data*2;
                tmp.step=cmp.step+1;
                a.push(tmp);
                vis[tmp.data]=true;
            }

        a.pop();
    }

    return 0;
}