例题9.1 Catch That Cow

//个人感觉BFS挺简单的，就调用一个函数就行
#include <iostream>
#include <queue>
#include <cstring>//memset
using namespace std;

struct Pos
{
   int pos;
   int t;
   Pos(int pos,int t):pos(pos),t(t){}
};

bool visit[100000];
void BFS(int n,int k)
{
    queue<Pos> q;
    Pos current(n,0);
    q.push(current);
    visit[n]=true;
    
    while(!q.empty())
    {
        Pos cur=q.front();
        q.pop();
        if(cur.pos==k){
             cout<<cur.t<<endl;
             break;
        }
        
        
        for(int i=1;i<=3;i++)
        {
            Pos nextpos(0,0);//必须要初始化
            if(i==1){
                nextpos.pos=cur.pos-1;
                nextpos.t=cur.t+1;
            }
            else if(i==2){
                nextpos.pos=cur.pos+1;
                nextpos.t=cur.t+1;
            }
            else
            {
                nextpos.pos=cur.pos*2;
                nextpos.t=cur.t+1;
            }
            if(nextpos.pos<0||nextpos.pos>100000||visit[nextpos.pos]==true)
            {
                continue;
            }
            q.push(nextpos);
            visit[nextpos.pos]=true;
        }
    }
        
}

int main()
{
    int m;cin>>m;
    int n,k;
    for(int i=1;i<=m;i++)
    {
        cin>>n>>k;
        memset(visit,false,sizeof(visit));
        BFS(n,k);
    } 
}