6043:哆啦A梦的时光机

• 描述
• 输入
• 输出
• 样例输入
• 样例输出
• 思路
• 代码

描述

总时间限制:  1000ms内存限制:  65536kB

哆啦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

思路

这道题一看就很水，是一道标准的搜索。我们可以用队列来水它。（注意清零）

代码

#include
#include//队列头文件
#include
using namespace std;
queue<int>a;//定义整数数列
const int MX=2000008;
int n,S,T,i,tmp;
int f[MX];
int main()
{scanf("%d",&n);for(int i=0;imemset(f,0,sizeof(f));while(!a.empty()) a.pop();//队列scanf("%d%d",&S,&T);a.push(S);//入队while(!a.empty())//判断队列是否为空{tmp=a.front();//定位到对头元素a.pop();//对头元素出队if(tmp+11]){a.push(tmp+1); f[tmp+1]=f[tmp]+1;if(tmp+1==T) break;}if(tmp>0&&!f[tmp-1]){a.push(tmp-1); f[tmp-1]=f[tmp]+1;if(tmp-1==T) break;}if(tmp*22]){a.push(tmp*2); f[tmp*2]=f[tmp]+1;if(tmp*2==T) break;}if(tmp%2==0&&!f[tmp/2]){a.push(tmp/2); f[tmp/2]=f[tmp]+1;if(tmp/2==T) break;}}printf("%d\n",f[T]*2);}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！