【Luogu1588】丢失的牛

problem

solution

codes

//BFS+记忆化搜索
#include<iostream>
#include<queue>
#include<cstring>
#define maxn 100000
using namespace std;
int f[maxn],ans;
int a, b;
void bfs(){
    memset(f,-1,sizeof f);
    queue<int>q; q.push(a); f[a]=0;
    while(q.size()){
        int x = q.front(),y; q.pop();
        if(x==b){ ans = f[b]; break; }
        y = 2*x; 
        if(y>=0&&y<maxn&&(f[y]==-1||f[y]>f[x]+1)){ f[y]=f[x]+1; q.push(y); }
        y = x-1;
        if(y>=0&&y<maxn&&(f[y]==-1||f[y]>f[x]+1)){ f[y]=f[x]+1; q.push(y); }
        y = x+1;
        if(y>=0&&y<maxn&&(f[y]==-1||f[y]>f[x]+1)){ f[y]=f[x]+1; q.push(y); }
    }
}
int main(){
    int t; cin>>t;
    while(t--){
        cin>>a>>b;
        bfs();
        cout<<ans<<"
";
    }
    return 0;
}