链接：

来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 32768K，其他语言65536K

64bit IO Format: %lld

题目描述

It’s universally acknowledged that there’re innumerable trees in the campus of HUST.

And there are many different types of trees in HUST, each of which has a number represent its type. The doctors of biology in HUST find 4 different ways to change the tree’s type x into a new type y:

1.    y=x+1

2.    y=x-1

3.    y=x+f(x)

4.    y=x-f(x)

The function f(x) is defined as the number of 1 in x in binary representation. For example, f(1)=1, f(2)=1, f(3)=2, f(10)=2.

Now the doctors are given a tree of the type A. The doctors want to change its type into B. Because each step will cost a huge amount of money, you need to help them figure out the minimum steps to change the type of the tree into B. 

Remember the type number should always be a natural number (0 included).

输入描述:

One line with two integers A and B

, the init type and the target type.

输出描述:

You need to print a integer representing the minimum steps.

示例1

输入

5 12

输出

3

说明

The minimum steps they should take: 5->7->10->12. Thus the answer is 3. 开始以为广搜会t，然而并不会

/*    data:2018.5.20    author:gsw    link:https://www.nowcoder.com/acm/contest/106#question*/#define ll long long#define IO ios::sync_with_stdio(false);#include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                using namespace std;#define maxn 1000005int brainy[maxn];int vis[maxn];int getbrainy(int a){ int ans=0; while(a>0) { if(a&1)ans++; a=a>>1; } return ans;}void init(){ for(int i=1;i
                
                  q; q.push(be); vis[be.x]=1; while(!q.empty()) { be=q.front(); q.pop(); if(be.x==b) { cout<
                 
                  <
                  
                   =0&&!vis[be.x-brainy[be.x]]) { vis[be.x-brainy[be.x]]=1; ne.x=be.x-brainy[be.x];ne.st=be.st+1; q.push(ne); } if((be.x-1)>=0&&!vis[be.x-1]) { vis[be.x-1]=1; ne.x=be.x-1;ne.st=be.st+1; q.push(ne); } if(!vis[be.x+brainy[be.x]]) { vis[be.x+brainy[be.x]]=1; ne.x=be.x+brainy[be.x];ne.st=be.st+1; q.push(ne); } }}int main(){ int a,b; init(); scanf("%d%d",&a,&b); bfs(a,b);}