首页 > 代码库 > openjudge 2971:抓住那头牛 解题报告
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，人品好。 这是关键。hhh
- 贴出代码。这个代码就非常简单了。
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 }
简直尴尬。
openjudge 2971:抓住那头牛 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。