POJ 3278 抓奶牛（BFS入门题）

描述

农夫约翰已被告知逃亡牛的位置，并希望立即抓住她。他开始于一个点Ñ（0≤ Ñ ≤100,000）上的数线和牛是在点ķ（0≤ ķ上相同数目的线≤100,000）。农夫约翰有两种交通方式：步行和传送。

*行走：FJ可以在一分钟内从任意点X移动到X -1或X + 1 点
*传送：FJ可以在一分钟内从任意点X移动到点2× X .

如果母牛不知道它的追求，根本不动，那么农夫约翰需要多长时间才能找回它？

输入

第1行：两个以空格分隔的整数：N和K.

产量

第1行：Farmer John捕捉逃亡牛所需的最短时间（以分钟为单位）。

样本输入

5 17

样本输出

暗示

农夫约翰到达逃亡牛的最快方法是沿着以下路径前进：5-10-9-18-17，这需要4分钟。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <queue>
 4 using namespace std;
 5 
 6 const int maxn=100005;
 7 int s,e;
 8 int d[maxn];
 9 
10 int bfs()
11 {
12     queue<int> que;
13     memset(d, 0x3f, sizeof(d));
14     d[s]=0;
15     que.push(s);
16 
17     while(que.size())
18     {
19         int t=que.front(); que.pop();
20         int dx[3]={1,-1,t};
21         if(t==e)
22             break;
23         for(int i=0; i<3; i++)
24         {
25             int nx=t+dx[i];
26             if(nx>=0 && nx<maxn && d[nx]==0x3f3f3f3f)
27             {
28                 que.push(nx);
29                 d[nx]=d[t]+1;
30             }
31         }
32     }
33     return d[e];
34 }
35 
36 
37  int main()
38  {
39      cin>>s>>e;
40      if(s>=e)
41         cout<<s-e<<endl;
42      else
43         cout<<bfs()<<endl;
44      return 0;
45  }

记住bfs函数如果有返回值，最好写成单一出口的那种，
不然编译器可能会提示：
用gcc编译一个程序的时候出现这样的警告：
warning: control reaches end of non-void function
它的意思是：控制到达非void函数的结尾。就是说你的一些本应带有返回值的函数到达结尾后可能并没有返回任何值。这时候，最好检查一下是否每个控制流都会有返回值。

POJ 3278 抓奶牛（BFS入门题）

相关推荐