poj 3278（hdu 2717） Catch That Cow（bfs）

Catch That Cow

Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 9753 Accepted Submission(s): 3054

Problem Description

Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.

* Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute
* Teleporting: FJ can move from any point X to the point 2 × X in a single minute.

If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?

Input

Line 1: Two space-separated integers: N and K

Output

Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.

Sample Input

5 17

Sample Output

Hint

The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes.

Source

USACO 2007 Open Silver

Recommend

teddy | We have carefully selected several similar problems for you: 1372 1072 1180 1728 1254

一道很简单的一维广搜题，将每次坐标变化存入队列，标记不重复即可。

题意：一个农民去抓一头牛，输入分别为农民和牛的坐标，农民每次的移动可以坐标+1，或者坐标-1，或者坐标乘2三种变化，假设牛不知道农民来抓它而一直呆在原地不动，农民最少需要几步才能抓到牛。

附上代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <queue>
 5 #define M 100005
 6 using namespace std;
 7 int n,m;
 8 int visit[M];    //标记数组，0表示没走过，1表示已走过
 9 struct node
10 {
11     int x,t;
12 } s1,s2;
13 void BFS()
14 {
15     queue<node> q;
16     while(!q.empty())
17         q.pop();
18     s1.x=n;
19     s1.t=0;
20     visit[n]=1;     //农民起始位置标记为已走过
21     q.push(s1);
22     while(!q.empty())
23     {
24         s1=q.front();
25         q.pop();
26         if(s1.x==m)   //结束标志为农民到了牛的位置
27         {
28             printf("%d
",s1.t);
29             return;
30         }
31         s2.x=s1.x+1;      //坐标+1
32         if(s2.x>=0&&s2.x<=M&&!visit[s2.x])  //判断变化后的数字是否超过了范围
33         {
34             visit[s2.x]=1;
35             s2.t=s1.t+1;
36             q.push(s2);
37         }
38         s2.x=s1.x-1;      //坐标-1
39         if(s2.x>=0&&s2.x<=M&&!visit[s2.x])
40         {
41             visit[s2.x]=1;
42             s2.t=s1.t+1;
43             q.push(s2);
44         }
45         s2.x=s1.x*2;      //坐标*2
46         if(s2.x>=0&&s2.x<=M&&!visit[s2.x])
47         {
48             visit[s2.x]=1;
49             s2.t=s1.t+1;
50             q.push(s2);
51         }
52     }
53 }
54 int main()
55 {
56     int i,j;
57     while(~scanf("%d %d",&n,&m))
58     {
59         memset(visit,0,sizeof(visit));    //开始全部定义为0
60         BFS();
61     }
62     return 0;
63 }