#I. 哆啦A梦的时光机(bfs经典习题)

news/2024/4/19 19:53:18/

题目

说明

有一天,大雄和他的伙伴们想穿越时空进行探险,可是时光机却出了一点故障,只能进行有限的时空穿越操作。大雄他们需要从现在出发,到达一个目标时间点进行探险,结束后再返回到现在,他们希望尽可能减少时光机的操作次数,你能帮助他们吗?

假设大雄和他的伙伴们出发的时间点(现在)为 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行,每一行一个正整数,表示每组测试数据对应的最少时光机操作次数。

样例

输入数据 1

2

5 17

4 8

输出数据 1

8

2

提示

对于 S=5,T=17:

操作如下:5->4->8->16->17->16->8->4->5

对于 S=4,T=8:操作如下:4->8->4


思路

建议先做信奥一本通1253抓住那头牛。

典型的数轴bfs问题

大雄和他的伙伴们可以从x 走到x ± 12xx/2,请问农夫大雄和他的伙伴们最少移动多少次就能到达t时刻

深搜很有可能会找不到答案。而且不一定搜到底,所以就想到广搜,求最少步数

把当前能到达位置加入队列,对于每个位置按次序往四个方向加入队列,然后用一个vis判断是否走过,当走到目标点时,输出步数

注意:在这里因为是往返2次,所以要bfs2次,一次是bfs(n,k) ,一次是bfs(k,n)

ps:


代码

#include <bits/stdc++.h>
using namespace std;
int vis[1000010],dx[5];
int n,k;
queue <int> q;
int bfs(int x,int k)
{while(!q.empty()) q.pop();memset(vis,0,sizeof(vis));vis[x] = 1;q.push(x);while(!q.empty()){int t = q.front();if(t == k) return vis[t];dx[0] = t + 1;dx[1] = t - 1;dx[2] = t * 2;int p = 3;if(t % 2 == 0) dx[3] = t / 2,p++;for(int i = 0; i < p; i++){if(dx[i] <= 1000000 && dx[i] >= 0 && vis[dx[i]] == 0){q.push(dx[i]);vis[dx[i]] = vis[t] + 1;}}q.pop();}
}
int main()
{int t;cin>>t;while(t--){cin>>n>>k;cout<<(bfs(n,k) - 1) + (bfs(k,n) - 1)<<'\n';}return 0;
}

http://www.ppmy.cn/news/317017.html

相关文章

PHP画a梦,html打造动漫人物--哆啦A梦

我相信每个人的童年都有一个哆啦a梦&#xff0c;一个小小的肚皮里装满了不可思议的哆啦a梦&#xff0c;一个在你无助伤心的时候陪在你身边的哆啦a梦&#xff0c;一个陪你胡思乱想陪你吃铜锣烧的哆啦a梦~今天我们就来画一个我们心中的哆啦a梦吧~ 定义哆啦a梦的容器千篇一律先定义…

qq空间显示手机型号android,qq说说显示手机型号 qq说说显示手机型号在哪里设置...

1、升级到最新版本的QQ空间; 2、切换到”我的空间“; 3、点左上角“设置”按钮; 4、有一个”我的手机标识“&#xff0c;点开你就可以选择了;QQ发表说说怎么不显示手机型号 1.首先我们打开手机QQ&#xff0c;在右下角找到“动态”&#xff0c;并点击进入; 2.在动态页面&#xf…

qq空间显示手机型号android,qq空间如何设置显示手机型号

在手机qq发表说说动态&#xff0c;是可以显示我们自己手机的型号&#xff0c;对于新手&#xff0c;可能不知道怎样设置&#xff0c;下面就让学习啦小编告诉大家qq空间如何设置显示手机型号。 qq空间设置显示手机型号的方法一&#xff1a;手机qq空间客户端 打开QQ空间&#xff0…

js 判断系统类型和手机型号(厂商)

要想判断手机类型(Android或者IOS)和手机型号(厂商等)&#xff0c;可以通过js的navigator.userAgent获取一些基本的信息&#xff0c;如我的红米的一些头信息&#xff1a; 红米 4X Mozilla/5.0 (Linux; Android 7.2; Redmi 4X Build/MMB29M; wv) AppleWebKit/537.36 (KHTML, li…

android 修改手机型号加点,修改Android设备信息,如修改手机型号为iPhone7黄金土豪版! -电脑资料...

首先你的手机必须要有ROOT权限&#xff0c;误操作有风险需谨慎 请先开启手机的USB调试&#xff0c;防止手机修改后无法启动时导致的无法修复 1、如果你是在手机上修改&#xff0c;直接使用RE文件管理器&#xff0c;编辑/system/build.prop文件&#xff0c;找到 ro.product.mode…

Qt for Android获取手机序列号/手机型号/手机制造商

前言 Qt for Android 获取手机型号/手机制造商/手机序列号,这些是要通过 Android 原生接口才能获取到的, 那么在 Qt 项目中通过 jni 接口调用 Android 原生接口来获取相应的值,之前已经写文章详细介绍如何在 Qt 工程中添加 java 文件然后实现 Android 接口的调用,在这里.那么这…

支持鸿蒙系统的手机名单,华为鸿蒙系统支持手机型号名单

鸿蒙系统已经能够更新了&#xff0c;这让华为的用户都非常的激动期待的想马上进行更新&#xff0c;那么整款国人之光系统到底支持哪些手机呢&#xff1f;下面就为大家带来了华为鸿蒙系统支持手机型号名单&#xff0c;快来一起看看吧。 鸿蒙系统支持哪些手机 鸿蒙系统支持的华为…

android 获取手机型号和系统版本,Android 获取imei号码,获取手机型号和系统版本号等信息...

在AndroidManifest.xml文件中要添加 才有权限 [javascript] TelephonyManager tm = (TelephonyManager) this.getSystemService(TELEPHONY_SERVICE); /* * 电话状态: * 1.tm.CALL_STATE_IDLE=0 无活动 * 2.tm.CALL_STATE_RINGING=1 响铃 * 3.tm.CALL_STATE_OFFHOOK…

ua获取手机型号_js获取移动端设备信息(IMEM,IMIS,手机型号,系统版本,浏览器信息等)...

方法一: HTML+ 封装好的方法,额外配置,使用指定方法打包才可用 属性: imei: 设备的国际移动设备身份码 imsi: 设备的国际移动用户识别码 model: 设备的型号 vendor: 设备的生产厂商 uuid: 设备的唯一标识 参考地址: http://www.html5plus.org/doc/zh_cn/device.html 方法…

JS获取手机型号和系统类型

1.获取手机的dpr:window.devicePixelRatio 手机以dpr2为标准 比如在dpr为2的手机 100px&#xff1b; 那么在dpr为3的手机应该为 100 * (3/2)px 2.判断手机类型或pc端和移动端 navigator.userAgent; 例子&#xff1a; <script> function isMobile() {var userAgenInfo …

Html5判断手机型号,WebView-修改userAgent用于网页端判断手机型号

//本文用于在userAgent后添加标识字段(dbios/版本号) 前言 H5页面获得的UserAgent都是默认的UserAgent,而不是修改后的UserAgent,原因在于webView会将userAgent替换为默认。 直接在加载webView处更改无效,故而我们在AppDelegate里面的- (BOOL)application:(UIApplication )a…

html获取手机型号,前端通过js获取手机型号

###前段通过js获取手机型号 需求: 用户登录后记录当前的手机型号并记录 插件: 使用步骤: 获取UA信息->根据安卓和IOS不同的处理 IOS再通过插件mobile-device-js去获取型号 安卓通过解析UA信息去获取build之前的信息得到手机型号 //引入插件 //获取userAgent信息 var user…

通过UA判断手机的类型

最近开发遇到一个需求&#xff0c;不同的手机上显示不同的内容&#xff1a; 需要区分ios系统&#xff0c;华为手机&#xff0c;三星手机&#xff0c;其他安卓手机&#xff08;因为ios有apple pay 、华为有huaweiPay、三星有samsungPay&#xff09; 实现方式&#xff1a; var …

判断手机类型

var u navigator.userAgent;var isAndroid u.indexOf(Android) > -1 || u.indexOf(Adr) > -1; //android终端var isiOS !!u.match(/\(i[^;];( U;)? CPU.Mac OS X/); //ios终端//alert(是否是Android&#xff1a;isAndroid);//alert(是否是iOS&#xff1a;isiOS);if(i…

pandas---数据结构(Series、DataFrame 和 MultiIndex)创建方式、属性

1. 数据结构 Pandas中一共有三种数据结构&#xff0c;分别为&#xff1a;Series、DataFrame 和MultiIndex。 其中Series是一维数据结构&#xff0c;DataFrame是二维表格型数据结构&#xff0c;MultiIndex是三维数据结构。 1.1 Series Series是一个类似于一维数组的数据结构…

笔记本开机风扇狂转但无法开机

可能是内存出了问题&#xff0c;将内存取出清理金手指后插回。本人遇到的情况是一台使用了七年的笔记本&#xff0c;中间加过一次内存条&#xff0c;老内存条坏了开不了机&#xff0c;把后来装的内存条装到老内存条的位置……

电脑cpu风扇转一下就停,不停重复,无法开机。

其实这个问题很简单。 从简单的开始排除&#xff0c; 1&#xff0c;检查内存条&#xff0c;擦一下金属脚即可。 2&#xff0c;把主板电池放电。 如果上面2个方法还是无法解决问题。 3&#xff0c;直接换掉电源就可以搞定。 我试验过。就这样结局问题的。 希望能帮到大家…

Win10关机后机箱风扇还一直转

在台式机上安装Win10之后&#xff0c;发现关机时&#xff0c;屏幕&#xff0c;硬盘都已经关闭&#xff0c;但是主机里面的散热风扇还是一直转个不停&#xff0c;电源根本没有关闭&#xff0c;有一种情况是关机的策略组的设置问题&#xff0c;可以试一下。 依次点击“开始”→“…

【转】笔记本电脑开机电源指示灯亮,但黑屏,风扇不转,无任何运行迹象!...

一般这个都是驻电产生的&#xff0c; 需要先放电&#xff0c;然后试着开机。 笔记本放电方法&#xff1a; 1.拔下电源适配器 2.拔下电池 3.按住电源按钮&#xff0c;30秒以上&#xff08;具体时间根据具体笔记本而定&#xff09; 如果不能解决&#xff0c;有可能是主板供电出问…

神州战神笔记本风扇一直转

场景&#xff1a;不知道按了什么键&#xff0c;导致风扇一直转 解决方法&#xff1a;可以尝试按FN1&#xff0c;根据网友反馈&#xff0c;此快捷键可进入强制制冷模式