/**
***= =,好吧我来翻译一下,就是有2个数A,B。A可以+1,-1,*2来改变自己的值,上面三种情况都算作操作+1。求A=B所用的最少的操作数。。。。。(0<A,B<100000).
----此题来自百练poj
A:Catch That Cow
查看 提交 统计 提问
总时间限制: 2000ms 内存限制: 65536kB
描述
Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately.
He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000)
on the same number line. Farmer John has two modes of transportation: walking and teleporting.
* Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute
* Teleporting: FJ can move from any point X to the point 2 × X in a single minute.
If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?
输入
Line 1: Two space-separated integers: N and K
输出
Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.
*/
#include<iostream>
#include<queue>
#include<string.h>//memset()
using namespace std;
int getMinStepsByBFS(int n,int k){
int xSteps[100001];
memset(xSteps,0,sizeof(xSteps));//这里将所有的该范围内的数都包含,内容为0即未操作过,否则在原来的基础上+1
queue<int> points;//此队列是用来存要进行操作的点
points.push(n);
while(!points.empty()){
int x = points.front();
if(x == k){
return xSteps[k];//广度搜索搜一次就能搜到最优解,因为他是在所有操作数相同的情况下最先搜到的
}else{
points.pop();
for(int i = 0;i < 3;i++){
switch(i){
case 0 :
if(x-1>= 0 && !xSteps[x-1] && x-1!=n){
xSteps[x-1] = xSteps[x]+1;
points.push(x-1);
}
break;
case 1 :
if(x-1 <= 100000 && !xSteps[x+1] && x+1!=n){
xSteps[x+1] = xSteps[x]+1;
points.push(x+1);
}
break;
case 2 :
if(2*x <= 100000 && !xSteps[2*x] && 2*x!=n){
xSteps[2*x] = xSteps[x]+1;
points.push(2*x);
}
break;
default :
cout<<"error"<<endl;
}
}
}
}
}
int main(){
int n,k;
cin>>n>>k;
if(n>=0 && n<=100000 && k>=0 && k<= 100000){
cout<<getMinStepsByBFS(n,k)<<endl;
}
system("pause");
return 0;
}
相关推荐
WEB程序设计大作业 实现多个网页的互联功能 界面漂亮 实用
C++程序设计语言作业题
mfc可视化程序设计的大作业俄罗斯方块,windows应用程序,visual studio2013下开发
《软件工程》大型作业-网上书店管理系统分析、设计及实现
本系统实现的主要功能就是学生在线提交实验报告,教师在线批阅实验报告的功能。用PHP语言开发完成,文档内容结构如下: 1系统分析 1.1功能 1.2解决方案 2.系统设计 2.1.1系统流程图 2.1.2 应用程序的文件描述 ...
2013级,C++程序设计课件。第3章 程序设计初步。内容: 3.1 面向过程程序设计和算法 3.2 C++程序和语句 3.3 赋值语句 3.4 C++的输入与输出 3.5 编写顺序结构的程序 3.6 关系运算和逻辑运算 3.7 选择结构和 if 语句 ...
程序设计语言 实践之路 第3版 英文原版 包含PDF,CHM,CD,源码
习题集内容覆盖面广,包括:Java言的基本常识、基本语法、面向对象的基本概念、数组、字符串、异常处理、文件和数据流、图形用户界面设计、小应用程序、线程、编程规范、网络程序设计、多媒体民图形学程序设计以及...
《C++程序设计教程》(修订版)—设计思想与实现 钱能著 课后习题答案详解、源代码
要求:1、用C语言实现程序设计; 2、利用结构体数组、链表等实现学生信息表达、查询等,充分体现数据结构的知识; 3、系统的各个功能模块要求用函数的形式实现; 4、界面友好(良好的人机交互),程序要有注释。 5、...
研究生网络编程作业,所有的结构与代码均由自己实现,适合用于上交老师布置的聊天程序编写作业
北京大学信息科学技术学院的课程程序设计实习的大作业魔兽世界终极版的源代码,仅供参考。
为适应计算机基础不同的读者学习与欣赏,对有些趣题采用多种思路设计与多个程序实现。其中少量难度较大、要求较高的问题在目录中用“*”标注,可供在校学习“C程序设计”课程的同学们进行课程设计时选用。 《趣味C...
实战MATLAB之并行程序设计
《PHP与MySQL程序设计 第4版 》pdf与源码 是全面讲述PHP与MySQL的经典之作 书中不但全面介绍了两种技术的核心特性 还讲解了如何高效地结合这两种技术构建健壮的数据驱动的应用程序 《PHP与MySQL程序设计 第4版 》...
张玉生《C语言程序设计》双色版 教材课后习题答案,仅供参考,大家一定要自己做一遍再校对答案,实验书的答案已经以文章的形式发布了。
WPF程序设计指南(最全-清晰PDF中文版-附源码) (文件太大,分成三个部分) 跟随Windows大师Charles Petzold学习新一代Windows客户端接口程序设计 Windows Presentation Foundation(WPF)是微软.NET Fmmework 3.0...
GDI+程序设计.pdf,书籍和随书源码。
第3章 设计与实现 48 3.1 马尔可夫链算法 48 3.2 数据结构的选择 50 3.3 在C中构造数据结构 51 3.4 生成输出 54 3.5 Java 56 3.6 C++ 59 3.7 Awk和Perl 61 3.8 性能 63 3.9 经验教训 64 第4章 界面 67 4.1 逗号分隔...
《C程序设计语言<第2版新版>习题解答(原书第2版)》是对Brian W.Kernighan和Dennis M.Ritchie所著的《C程序设计语言<第2版新版>习题解答(原书第2版)》所有练习题的解答,是极佳的编程实战辅导书。K&R的著作是C语言...