抓住那头牛

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

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

农夫有两种移动方式:

  1. 从 X 移动到 X−1 或 X+1,每次移动花费一分钟
  2. 从 X 移动到 2∗X,每次移动花费一分钟

假设牛没有意识到农夫的行动,站在原地不动。

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

输入格式

共一行,包含两个整数N和K。

输出格式

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

数据范围

0≤N,K≤1e5

输入样例:

5 17

输出样例:

4

#include<iostream>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
int n,k;
int res;
map<int,int> mp;
int bfs(int st,int ed)
{
    queue<int> q;
    q.push(st);
    mp[st]=0;
    while(q.size())
    {
        int a,b,c;
        int t=q.front();
        q.pop();
        if(t==ed) return mp[ed];
        if(!mp[t*2]&&t<=1e5)
        {
            mp[t*2]=mp[t]+1;
            q.push(t*2);
        }
        if(!mp[t+1]&&t<=1e5)
        {
            mp[t+1]=mp[t]+1;
            q.push(t+1);
        }
        if(!mp[t-1]&&t)
        {
            mp[t-1]=mp[t]+1;
            q.push(t-1);
        }
    }
    return -1;
}
int main()
{
    cin>>n>>k;
    cout<<bfs(n,k)<<endl;
    return 0;
}