题目描述
FJ 丢失了他的一头牛，他决定追回他的牛。已知 FJ 和牛在一条直线上，初始位置分别为 \(x\) 和 \(y\)，假定牛在原地不动。FJ 的行走方式很特别：他每一次可以前进一步、后退一步或者直接走到 \(2\times x\) 的位置。计算他至少需要几步追上他的牛。
输入格式
第一行为一个整数 \(t\ ( 1\le t\le 10)\)，表示数据组数；
接下来每行包含一个两个正整数 \(x,y\ (0<x,y \le 10^5)\)，分别表示 FJ 和牛的坐标。
输出格式
对于每组数据，输出最少步数。
样例 #1
样例输入 #1
1
5 17
样例输出 #1
4
code:
#include <bits/stdc++.h>
using namespace std;
int vis[1000010];
queue <int> q;
void bfs(int a,int b){
while(!q.empty()) q.pop();//清空队列
q.push(a);
vis[a] = 0;
while(!q.empty()){
int x = q.front();
if(x == b){//满足条件就退出
cout<<vis[b]<<endl;
return;
}
q.pop();
if(!vis[x*2] and x <= 50001){
vis[x*2] = vis[x]+1;
q.push(x*2);
}if(!vis[x+1] and x <= 100001){
vis[x+1] = vis[x]+1;
q.push(x+1);
}if(!vis[x-1] and x > 1){
vis[x-1] = vis[x]+1;
q.push(x-1);
}
}
}
int main(){
int t;
cin>>t;
for(int i = 1;i<=t;i++){
int x,y;
cin>>x>>y;
memset(vis,0,sizeof(vis));//每次输入前清空数组
bfs(x,y);
}
return 0;
}