题目描述

描述

哆啦A梦有一个神奇的道具：时光机。坐着它，大雄和他的伙伴们能穿越时空，回到过去或者去到未来。

有一天，大雄和他的伙伴们想穿越时空进行探险，可是时光机却出了一点故障，只能进行有限的时空穿越操作。大雄他们需要从现在出发，到达一个目标时间点进行探险，结束后再返回到现在，他们希望尽可能减少时光机的操作次数，你能帮助他们吗？
假设大雄和他的伙伴们出发的时间点（现在）为S（0 < S < 1,000,000），希望到达的时间点（目标）为T（0 < T < 1,000,000），已知时光机可以进行如下的时空穿越操作（X为正整数）：
可以从任意时刻X穿越到X+1或者X-1时刻
可以从任意时刻X穿越到X*2时刻
当X为偶数时，可以从X时刻穿越到X/2时刻
请问，大雄和他的伙伴们从S时刻出发，先到达T时刻，再回到S时刻最少需要多少次时空穿越操作？

输入

输入的第一个数是一个正整数N，表示测试数据一共有N组（0 < N < 20）。
之后有N行，每一行包含两个正整数S和T，表示出发和到达时间点。S≠T

输出

输出包括N行，每一行一个正整数，表示每组测试数据对应的最少时光机操作次数。

样例输入

2
5 17
4 8

样例输出

8
2

提示

对于S=5，T=17：
操作如下：5->4->8->16->17->16->8->4->5
对于S=4，T=8：
操作如下：4->8->4

题目分析

这是一道十分类似BFS的走迷宫的题，给一个数X就可以使用一步的时间分支出X-1,X+1,X*2,X/2(当X%2==0时)四或三种走法。依次枚举得到最小步骤再*2即可。

代码实现

//之前写复杂了可以批评指正
#include<iostream>
#include<cstring>
using namespace std;
int S,head=0,tail=1,a[1000005],q,cont[1000005],c=0,x[3]={
   1,-1};
bool b[1000005];
void print(int d)
{if(cont[d]!=0)print(cont[d]);//printf("%d\n",a[d]);c++;
}
void dfs(int n,int k)
{memset(b,0,sizeof(b));memset(a,0,sizeof(a));memset(cont,0,sizeof(cont));a[1]=n;b[n]=1;head=0;tail=1;while(head!=tail){head++;x[2]=a[head];for(int i=0;i<=3;i++){if(i==3){if(a[head]%2==0)q=a[head]/2;else break;}else q=a[head]+x[i];if(!b[q]&&q<=1000000&&q>=0){   tail++;a[tail]=q;cont[tail]=head;b[q]=1; if(a[tail]==k){print(tail);c--;return ;}}}}
}
int main()
{int n,k;scanf("%d",&S);for(int j=1;j<=S;j++){c=0;scanf("%d%d",&n,&k);dfs(n,k);dfs(k,n);printf("%d\n",c);}
}