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，人品好。  這是關鍵。

代碼如下：

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:抓住那頭牛的解題過程是什么內容對大家有幫助，同時也希望大家多多支持億速云，關注億速云行業資訊頻道，遇到問題就找億速云，詳細的解決方法等著你來學習!