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 }

　　

#簡直是尷尬。

 相關教學：

C 影片教學

以上是openjudge 2971:抓住那頭牛 解題過程（附代碼）的詳細內容。更多資訊請關注PHP中文網其他相關文章！