Catch That Cow

农夫知道一头牛的位置，想要抓住它。农夫和牛都于数轴上 ，农夫起始位于点 N(0<=N<=100000) ，牛位于点 K(0<=K<=100000) 。农夫有两种移动方式： 1、从 X移动到 X-1或X+1 ，每次移动花费一分钟 2、从 X移动到 2*X ，每次移动花费一分钟 假设牛没有意识到农夫的行动，站在原地不。最少要花多少时间才能抓住牛？
Input
一行: 以空格分隔的两个字母: N 和 K
Output
一行: 农夫抓住牛需要的最少时间，单位分钟
Sample Input
5 17
Sample Output
4
Hint
农夫使用最短时间抓住牛的方案如下: 5-10-9-18-17, 需要4分钟.
这道题目就是要自己心中构造一个图，以前做的题目都是二维的图，这次是一个一维的遍历。
然后有三种情况。分别是前进一步，后退一步，前进二倍的步数。

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
const int maxn = (int)1e5 + 10;
int n, k;
int vis[maxn];
struct node{
int x, t;
friend bool operator < (node a, node b){
return a.t > b.t;
}
};
void BFS(int x1, int x2){
memset(vis, 0, sizeof(vis));
priority_queue <node> que;
node e1, e2;
e1.x = x1; e1.t = 0;
vis[e1.x] = 1;
que.push(e1);
while (!que.empty()){
e1 = que.top();
que.pop();
if (e1.x == x2) break;
else
{
if(e1.x-1>0&&vis[e1.x-1]==0)
{
e2.x=e1.x-1;
e2.t=e1.t+1;
vis[e2.x]=1;
que.push(e2);
}
if(e1.x+1<=100000&&vis[e1.x+1]==0)
{
e2.x=e1.x+1;
e2.t=e1.t+1;
vis[e2.x]=1;
que.push(e2);
}
if(e1.x*2<=100000&&vis[e1.x*2]==0)
{
e2.x=e1.x*2;
e2.t=e1.t+1;
vis[e2.x]=1;
que.push(e2);
}
}
}
printf ("%dn", e1.t);
}
int main()
{
while(scanf ("%d %d", &n, &k)!= EOF){
if (n > k) printf("%dn", n - k);
else
BFS(n, k);
}
return 0;
}

这次的代码写的不太好看。。

最后

以上就是健忘云朵为你收集整理的Catch That Cow的全部内容，希望文章能够帮你解决Catch That Cow所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。