哆啦A梦的时光机
哆啦A梦有一个神奇的道具：时光机。坐着它，大雄和他的伙伴们能穿越时空，回到过去或者去到未来。 讯享网
讯享网有一天，大雄和他的伙伴们想穿越时空进行探险，可是时光机却出了一点故障，只能进行有限的时空穿越操作。大雄他们需要从现在出发，到达一个目标时间点进行探险，结束后再返回到现在，他们希望尽可能减少时光机的操作次数，你能帮助他们吗？ 假设大雄和他的伙伴们出发的时间点（现在）为S，希望到达的时间点（目标）为T，已知时光机可以进行如下的时空穿越操作（X为正整数）： 可以从任意时刻X穿越到X+1或者X-1时刻 可以从任意时刻X穿越到X*2时刻 当X为偶数时，可以从X时刻穿越到X/2时刻 请问，大雄和他的伙伴们从S时刻出发，先到达T时刻，再回到S时刻最少需要多少次时空穿越操作？
Input
输入的第一个数是一个正整数N，表示测试数据一共有N组。 之后有N行，每一行包含两个正整数S和T，表示出发和到达时间点。S≠T Output
讯享网输出包括N行，每一行一个正整数，表示每组测试数据对应的最少时光机操作次数。
Sample Input
25 174 8 Sample Output
讯享网82
Range
0 < N < 20;0 < T < 1,000,000;0 < S < 1,000,000;
Explain
对于S=5，T=17： 操作如下：5->4->8->16->17->16->8->4->5 对于S=4，T=8： 操作如下：4->8->4 Code and Analysis
讯享网代码如下： //广度优先搜索（哆啦A梦的时光机） #include<cstdio> #include<cstring> //使用清空函数要用这个头文件 #include<queue> //队列头文件queue using namespace std; //队列头文件要带这个 queue<int>a; //定义队列a 格式为：queue<队列类型>变量名; int n,s,t,f[],i,tmp; int main() { scanf("%d",&n); for(i=0;i<n;i++) { while(!a.empty()) a.pop(); //用循环清空队列a； memset(f,0,sizeof(f)); scanf("%d%d",&s,&t); a.push(s); //s入队 //下面开始广度优先搜索 while(!a.empty()) //判断队列是否为空 { tmp=a.front(); //返回队首元素值 a.pop(); //删除队首元素 if(tmp+1<&&!f[tmp+1]) //判断数组元素是否越界，且判断这里有没有数 { a.push(tmp+1); f[tmp+1]=f[tmp]+1; if(tmp+1==t) break; //找到t后跳出循环 } //X+1的情况 if(tmp>0&&!f[tmp-1]) //判断数组元素是否为正 { a.push(tmp-1); f[tmp-1]=f[tmp]+1; if(tmp-1==t) break; } //X-1的情况 if(tmp*2<&&!f[tmp*2]) //判断数组元素是否越界 { a.push(tmp*2); f[tmp*2]=f[tmp]+1; if(tmp*2==t) break; } //X*2的情况 if(tmp%2==0&&!f[tmp/2]) //判断tmp的奇偶 { a.push(tmp/2); f[tmp/2]=f[tmp]+1; if(tmp/2==t) break; } //X/2的情况 } printf("%d\n",f[t]*2); //因为是来回，所以是两倍 } }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/33640.html