这一篇题解写给刚刚学习宽搜的同学，记得当时刚学时看题解基本都是一句话：这题裸的宽搜啊，当时一脸绝望。。。

本篇题解延续个人风格，细致的讲解：各位大佬可以跳过，直接看代码找本题坑点也行。

题目描述

FJ丢失了他的一头牛，他决定追回他的牛。已知FJ和牛在一条直线上，初始位置分别为x和y，假定牛在原地不动。FJ的行走方式很特别：他每一次可以前进一步、后退一步或者直接走到2*x的位置。计算他至少需要几步追上他的牛。

输入输出格式

输入格式：

第一行为一个整数t(≤10)，表示数据组数；接下来每行包含一个两个正整数x和y(0<x,y≤10^5)，分别表示FJ和牛的坐标。

输出格式：

对于每组数据，输出最少步数。

输入输出样例

输入样例#1： 复制

1 
5 17

输出样例#1： 复制

4

首先先来明确一下什么是宽搜？

通俗来说，宽搜就是从一个点开始扩展，将所能延伸到的点记录下来，当不能延伸时就对下一个点重复这个操作，直到找到最先满足条件的解为止（反正我是这么理解的。。。）

那么对于这一道题来说，一个点所能延伸出来的点只有+1，-1，*2，那么我们就可以开一个队列（手写也是可以的，但是为了省事就用STL吧。。。），从起点开始延伸，遇到没有走过的点就加入队列，并记录走了多少步，那么为什么走过的点不加呢？（因为如果之前走过，那么之前走肯定比现在走得到的解更优），当遇到第一个走到的位置达到终点是跳出并输出当时走了多少步即可。

差不多就这些了吧。。。

最后，附上本题代码（有详解）：

 1 #include<cstdio>
 2 #include<queue>
 3 #include<cstring>
 4 using namespace std;
 5 queue<int>q;
 6 const int maxn= 1e5+5;
 7 int dis[maxn];//dis表示走到目前位置最少走了多少步 
 8 void bfs(int s,int y)
 9 {
10     int x;
11     while(!q.empty())//多组询问常规清空操作 
12     {
13         q.pop();
14     }
15     memset(dis,0x5a5b5c4f,sizeof(dis));//初值设为inf，省去一个vis数组的空间 
16     dis[s]=0;
17     q.push(s);
18     while(!q.empty())//bfs模板 
19     {
20         x=q.front();
21         q.pop();
22         if(x==y)//满足条件跳出 
23         {
24             printf("%d\n",dis[y]);
25             return;
26         }
27         if(x+1<=maxn&&dis[x+1]==dis[0])//以dis[0]作为判断依据，也就是inf。判断该点是否走过，注意不要走出maxn 
28         {
29             dis[x+1]=dis[x]+1,q.push(x+1);
30         }
31         if(x-1>0&&dis[x-1]==dis[0])//x-1>0 比较显然吧，如果小于0你会RE，如果等于0你的dis[0]就会被更新，你整个程序就会崩掉 
32         {
33             dis[x-1]=dis[x]+1,q.push(x-1);
34         }
35         if(x*2<=maxn&&dis[x*2]==dis[0])//不复读了。。。 
36         {
37             dis[x*2]=dis[x]+1,q.push(x*2);
38         }
39     }
40 }
41 int main()
42 {
43     int t;
44     int x,y;
45     scanf("%d",&t);
46     for(int i=1; i<=t; i++)
47     {
48         scanf("%d%d",&x,&y);
49         bfs(x,y);
50     }
51     return 0;
52 }