呓语 | 杨英明的个人博客

专注于c++、Python,欢迎交流

By

poj 3278:Catch That Cow(简单一维广搜)

Catch That Cow
Time Limit: 2000MS   Memory Limit: 65536K
Total Submissions: 45648   Accepted: 14310

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 - 1 or + 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

4

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

 
  简单一维广搜
  题意
  你在一个一维坐标的n位置,牛在k位置,你要从n到k,抓到那头牛。你可以有三种走法,n+1,n-1,或者n*2直接跳。求你抓到那头牛的最短步数。
  思路
  简单广搜的思想。状态跳转的时候有三种跳转的方式,将新的状态放到队列中,再不断提取队列中最前面的状态,直到找到k位置。
  代码
 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <queue>
 5 using namespace std;
 6 
 7 bool isw[100010];
 8 
 9 struct Node{
10     int x;
11     int s;
12 };
13 
14 bool judge(int x)
15 {
16     if(x<0 || x>100000)
17         return true;
18     if(isw[x])
19         return true;
20     return false;
21 }
22 
23 int bfs(int sta,int end)
24 {
25     queue <Node> q;
26     Node cur,next;
27     cur.x = sta;
28     cur.s = 0;
29     isw[cur.x] = true;
30     q.push(cur);
31     while(!q.empty()){
32         cur = q.front();
33         q.pop();
34         if(cur.x==end)
35             return cur.s;
36         //前后一个个走
37         int nx;
38         nx = cur.x+1;
39         if(!judge(nx)){
40             next.x = nx;
41             next.s = cur.s + 1;
42             isw[next.x] = true;
43             q.push(next);
44         }
45         nx = cur.x-1;
46         if(!judge(nx)){
47             next.x = nx;
48             next.s = cur.s + 1;
49             isw[next.x] = true;
50             q.push(next);
51         }
52         //向前跳
53         nx = cur.x*2;
54         if(!judge(nx)){
55             next.x = nx;
56             next.s = cur.s + 1;
57             isw[next.x] = true;
58             q.push(next);
59         }
60     }
61     return 0;
62 }
63 
64 
65 int main()
66 {
67     int n,k;
68     while(scanf("%d%d",&n,&k)!=EOF){
69         memset(isw,0,sizeof(isw));
70         int step = bfs(n,k);
71         printf("%d\n",step);
72     }
73     return 0;
74 }

 

Freecode : www.cnblogs.com/yym2013

##原创声明 **转载请注明:[呓语](http://www.yangyingming.com) » [poj 3278:Catch That Cow(简单一维广搜)](http://www.yangyingming.com/article/57)**