openjudge 2971:抓住那头牛 解题过程（附代码）

总时间限制: 2000ms

内存限制: 65536kB

描述

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

1、从X移动到X-1或X+1，每次移动花费一分钟。

2、从X移动到2*X，每次移动花费一分钟。

假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？

输入

两个整数，N和K

输出

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

样例输入

5 17

样例输出

4

这道题就是一道水题。但是。它非常的坑。总结一下BFS就是

1，数组开够。

2，牛和老夫的方向判断。

3，重复入队的判断。

4，超界的判断。

5，人品好。 这是关键。

代码如下：

1 #includecstdio>
     2 #includealgorIThm>
     3 using namespace std;
     4 int x,y;
 5 struct node 6 {
     7     int x,times;
 8 }
    ;
     9 node q[3000010];
    10 int visit[1000010];
    11 int heads=1,last=1;
12 int main()13 {
    14     scanf("%d%d",&
    x,&
    y);
15     if(yx)16     {
    17     　　PRintf("%d",x-y);
    18     　　return 0;
19     }
    20     node a;
    21     a.x=x;
    a.times=0;
    22     q[heads]=a;
23     while(heads=last)24     {
    25     　　node n=q[heads];
    26     　　heads++;
27     　　if(n.x==y)28     　　{
    29         　　printf("%d",n.times);
    30         　　break;
31     　　}
    32     　　node n1=n;
    33    　　 n1.times++;
    34    　　 n1.x+=1;
    35     　　if(!visit[n1.x])q[++last]=n1 , visit[n1.x]=1;
    36     　　n1.x-=2;
    37     　　if(!visit[n1.x])q[++last]=n1 , visit[n1.x]=1;
    38     　　n1.x+=1;
    39     　　n1.x*=2;
    40     　　if(n1.x=100000&
    &
    !visit[n1.x])q[++last]=n1 , visit[n1.x]=1;
41     }
    42     return 0;
43 }
    　　

简直尴尬。

相关教程：C++视频教程

以上就是openjudge 2971:抓住那头牛 解题过程（附代码）的详细内容，更多请关注其它相关文章！

声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！