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 #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 }  　　

简直尴尬。

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

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