当前位置:首页 > 搜索 > 广度优先搜索 > 正文
NOI2.5-2971抓住那头牛
4197+

题目大意:在数轴上,从一个点到另外一个点有3种方法,分别是加1减1和乘2,请问从x点到y点,至少走多少步?

题目描述

农夫知道一头牛的位置,想要抓住它。农夫和牛都位于数轴上,农夫起始位于点N(0<=N<=100000),牛位于点K(0<=K<=100000)。农夫有两种移动方式:

1、从X移动到X-1或X+1,每次移动花费一分钟
2、从X移动到2*X,每次移动花费一分钟
假设牛没有意识到农夫的行动,站在原地不动。农夫最少要花多少时间才能抓住牛?

输入

两个整数,N和K

输出

一个整数,农夫抓到牛所要花费的最小分钟数

样例输入

5 17

样例输出

4

解题思路

广度优先搜索,先确定1步能到的点,再确定2步能到的点……直到k点的步数确定下来就结束。这样到底k点的步数就是最少的。

一般题目问最少步数,广搜会比深搜快很多。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,

NOI2.5-2971抓住那头牛:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!