人生第一道做出来的BFS题，这道题很适合入门的BFS

个人解析

　　通过这道题，我对BFS认识多点理解，

　　BFS的过程其实可以看成一棵树，树的孩子就是我们采取的不同方式，本题就可以看成一棵三叉树

　　注意边界情况，不要越界

　　

 

#include<bits/stdc++.h>
using namespace std;
queue<int> q;//设置队列一定要设为全局变量
int dis[100000];//记录走到当前位置至少走了多少步
void bfs(int x,int y)
{
    while(!q.empty()){
        q.pop();//清空数组
    }
    q.push(x);
    memset(dis,100000,sizeof(dis));
    dis[x]=0;
    while(!q.empty()){
        x=q.front();//模板，接受值，弹出
        q.pop();
        if(x==y){
            cout<<dis[y]<<endl;
            break;
        }
        if(x+1<100000&&dis[x+1]==dis[0]){//第一个判断是否越界，第二个判断是否走过
            dis[x+1]=dis[x]+1;
            q.push(x+1);
        }
        if(x-1>0&&dis[x-1]==dis[0]){
            dis[x-1]=dis[x]+1;
            q.push(x-1);
        }
        if(x*2<100000&&dis[2*x]==dis[0]){
            dis[2*x]=dis[x]+1,
            q.push(x*2);
        }
    }
}
int main()
{
    int t;
    cin>>t;
    while(t--){
        int x,y;
        cin>>x>>y;
        bfs(x,y);
    }
    return 0;
}