首页 > 其他 > 详细

hdu 2717 Catch That Cow(广搜bfs)

时间:2015-02-18 18:46:40      阅读:354      评论:0      收藏:0      [点我收藏+]

题目链接:http://i.cnblogs.com/EditPosts.aspx?opt=1

Catch That Cow

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


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
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.
 
今晚是大年三十除夕夜,在这里祝愿大家新年快乐!在新的一年里,开开心心,工作顺利,学习更上一层楼~n(*≧▽≦*)n
 
题目大意:在一个数轴上有n和k,农夫在n这个位置,奶牛在k那个位置,农夫要抓住奶牛,有两种方法:1、walking即农夫可以走x+1的位置和x-1的位置。
2、teleporting即每分钟可以走到2*x的位置。利用这两种方法,找到最快几步可以到达!
 
解题思路:其实就这三种情况,本来没打算用搜索的,不过发现好多东西都可以灵活运用!我们吧第一种方法看成两个方向,用dir[2]={1,-1,}表示,然后进行广搜!第二种方法自然就要特殊判断一下了!有一个地方要特殊判断一下,就是因为数据比较大,vis[ss.x]可能会超范围导致RE,所以都加一行判断使其保证在题目范围中。
 
详见代码。
 
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cmath>
 5 #include <queue>
 6 
 7 using namespace std;
 8 
 9 int dir[3]= {1,-1};
10 
11 struct node
12 {
13     int x,step;
14 } s,ss;
15 
16 int bfs(int n,int k)
17 {
18     queue<node>q,qq;
19     s.x=n;
20     s.step=0;
21     int vis[100010]= {0};
22     q.push(s);
23     while (!q.empty())
24     {
25         s=q.front();
26         q.pop();
27         if (s.x==k)
28             return s.step;
29         for (int i=0; i<2; i++)
30         {
31             ss.x=s.x+dir[i];
32             ss.step=s.step+1;
33             if (ss.x>=0&&ss.x<=100000)
34                 if (!vis[ss.x])
35                 {
36                     vis[ss.x]=1;
37                     q.push(ss);
38                 }
39         }
40         ss.x=s.x*2;
41         ss.step=s.step+1;
42         if (ss.x>=0&&ss.x<=100000)
43         {
44             if (!vis[ss.x])
45             {
46                 vis[ss.x]=1;
47                 q.push(ss);
48             }
49         }
50     }
51     return 0;
52 }
53 
54 int main ()
55 {
56     int n,k;
57     while (~scanf("%d%d",&n,&k))
58     {
59         printf ("%d\n",bfs(n,k));
60     }
61     return 0;
62 }

 

 

hdu 2717 Catch That Cow(广搜bfs)

原文:http://www.cnblogs.com/qq-star/p/4295862.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!