3060 抓住那头奶牛

USACO

时间限制: 1 s

空间限制: 16000 KB

题目等级 : 黄金 Gold

题目描述

Description

农夫约翰被告知一头逃跑奶牛的位置，想要立即抓住它，他开始在数轴的N 点（0≤N≤100000），奶牛在同一个数轴的K 点（0≤K≤100000）。约翰有两种移动方式：1 分钟内从x 点移动到x+1 或x-1；1 分钟内从x 点移动到2x。假设奶牛不会移动，约翰抓住它需要多少时间？

输入描述

Input Description

一行两个整数N 和K，用空格隔开。

输出描述

Output Description

约翰抓住它需要的最少时间。

样例输入

Sample Input

5 17

样例输出

Sample Output

4

数据范围及提示

Data Size & Hint

见题目

思路：广搜。

1 #include
          
            2 using namespace std; 3 #include
           
             4 struct node{ 5     int x,step; 6 }cur,net; 7 queue
            
             s; 8 bool num[100000]; 9 int n,m;10 void bfs()11 {12     cur.x=n;13     cur.step=0;14     s.push(cur);15     num[n]=1;16     while(!s.empty() )17     {18         cur=s.front() ;19         s.pop() ;20         int a=cur.x;21         if(a*2>0&&a*2<=100000&&!num[a*2]&&a<=m)22         {23             if(a*2==m)24             {25                 cout<
             
              0&&a+1<=100000&&!num[a+1])34         {35             if(a+1==m)36             {37                 cout<
              
               0&&a-1<=100000&&!num[a-1])46         {47             if(a-1==m)48             {49                 cout<
               
                >n>>m;62 if(n>=m)63 {64 cout<