POJ 3278 BFS

BFS

这道题觉得比较适合BFS新手入门写，也许大家都以为最入门的BFS题是在二维图上搜索，但是这道题是线性搜索，更加简单

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　Catch That Cow

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 133836		Accepted: 41405

描述。

农夫约翰被告知一头逃亡母牛的位置，他想马上抓住她。他从数字行上的点N(0≤N≤100，000)开始，牛在同一数字行上的点K(0≤K≤100，000)处。农民约翰有两种交通方式：步行和远距运输。

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

如果母牛没有意识到自己的追求，根本不动，那么农夫约翰要多久才能把它取回来呢？

输入。

第1行：两个空格分隔的整数：N和K。
输出量。

第一行：农民约翰抓住逃亡的母牛所需的最少的时间，以分钟为单位。

Sample Input

5 17

Sample Output

Hint

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

解释：其实就是从a点进行三个操作，最少多少步到达b点

注意：1 如果a大于b，只能减

　　　2 if(next<0 || next>100000) continue;不然会运行时出错

1：队列stl

 1 int  bfs(int n,int m)
 2 {
 3     int head, next;
 4     q.push(n);
 5     step[n]=0;
 6     vis[n]=1;
 7 
 8     while(!q.empty())
 9     {
10         head=q.front();
11 
12         for(int i=0;i<3;i++)
13         {
14             if(i==0)
15             {
16                 next=head-1;
17             }
18             else if(i==1)
19             {
20                 next=head+1;
21             }
22             else
23             {
24                 next=head*2;
25             }
26             if(next<0 || next>100000) continue;
27 
28             if(!vis[next])
29             {
30                 q.push(next);
31                 step[next]=step[head]+1;
32                 vis[next]=1;
33             }
34             if(next==m)
35             {
36                 return step[next];
37             }
38         }
39         q.pop();
40     }
41 }

2：模拟duilie

 1 int BFS(int n,int m)
 2 {
 3     head=1,tail=1;
 4     q[head]=n;
 5 
 6     while(1)
 7     {
 8         step1=q[head];
 9         for(int i=1;i<=3;++i)
10         {
11             if(i==1)
12             {
13                 step2=step1+1;
14             }
15             else if(i==2)
16             {
17                 step2=step1-1;
18             }
19             else if(i==3)
20             {
21                 step2=step1*2;
22             }
23             if(step2<0 || step2>100000) continue;
24             if(b[step2]==0)
25             {
26                 b[step2]=1;
27                 tail++;
28                 q[tail]=step2;
29                 step[step2]=step[step1]+1;
30             }
31             if(step2==m)
32             {
33                 return step[step2];
34             }
35         }
36         head++;
37     }
38 }