P1588 [USACO07OPEN] Catch That Cow S
[USACO07OPEN] Catch That Cow S
题目描述
FJ 丢失了他的一头牛，他决定追回他的牛。已知 FJ 和牛在一条直线上，初始位置分别为 x x x 和 y y y，假定牛在原地不动。FJ 的行走方式很特别：他每一次可以前进一步、后退一步或者直接走到 2 × x 2\times x 2×x 的位置。计算他至少需要几步追上他的牛。
输入格式
第一行为一个整数 t ( 1 ≤ t ≤ 10 ) t\ ( 1\le t\le 10) t (1≤t≤10)，表示数据组数；
接下来每行包含一个两个正整数 x , y ( 0 < x , y ≤ 1 0 5 ) x,y\ (0<x,y \le 10^5) x,y (0<x,y≤105)，分别表示 FJ 和牛的坐标。
输出格式
对于每组数据，输出最少步数。
样例 #1
样例输入 #1
1
5 17
样例输出 #1
4
#include<bits/stdc++.h>
using namespace std;
const long long N=1000000;
long long n,k,T,ans;
long long vis[N],d[N],dx[3];
long long q[N],l,r;
void bfs(){
while(l<=r){
long long x=q[l];
if(x==k){
printf("%d\n",d[l]);
return;
}
dx[0]=x+1,dx[1]=x-1,dx[2]=x<<1;
for(long long i=0;i<3;i++)
if(dx[i]>=0&&dx[i]<N&&!vis[dx[i]])
q[++r]=dx[i],d[r]=d[l]+1,vis[dx[i]]=1;
l++;
}
}
int main(){
scanf("%d",&T);
while(T--){
memset(d,0,sizeof(d));
memset(vis,0,sizeof(vis));
l=r=1;
scanf("%d%d",&n,&k);
q[l]=n;
vis[n]=1;
bfs();
}
return 0;
}