openjudge 2971:捉住那头牛 解题历程（附代码）【C#.Net教程】,C++

本篇文章重要报告了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

样例输出

这道题就是一道水题。然则。它异常的坑。总结一下BFS就是

1，数组开够。

2，牛和老汉的方向推断。

3，反复入队的推断。

4，超界的推断。

5，品德好。这是症结。

代码以下：

1 #include<cstdio>
 2 #include<algorithm>
 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(y<x)
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 }

几乎为难。