作者:pengwei8751150 | 来源:互联网 | 2023-05-19 06:38
题目链接:http:acm.hdu.edu.cnshowproblem.php?pid2717CatchThatCowTimeLimit:50002000MS(Java
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2717
Catch That Cow
Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 12615 Accepted Submission(s): 3902
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
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.
题目大意:在一条笔直的道路上,有一个农夫在A位置,一头牛在B位置,农夫一次可以搜索三个位置(例如农夫在x位置,他可以搜索x-1、x+1、x*2)问农夫至少需要几步能够找到牛。
解题思路: 用广搜 ,定义一个位置数组,每次搜索三个位置即可。
AC代码:
1 #include
2 #include <string.h>
3 #include
4 #include
5 #include
6 #include
7 using namespace std;
8 int f[200020]; //记录步数
9 void bfs(int n,int k)
10 {
11 int a[3]; //位置数组
12 memset(f,0,sizeof(f));
13 queue <int > q;
14 q.push(n);
15 f[q.front()] = 1;
16 if (n == k)
17 return ;
18 while (!q.empty())
19 {
20 int t = q.front();
21 int x = f[t];
22 a[0] = t-1; //三个位置
23 a[1] = t+1;
24 a[2] = t*2;
25 for (int i = 0; i <3; i ++)
26 {
27 if (a[i] >= 0 && a[i] <200001 && f[a[i]]==0) //注意这里的边界值
28 {
29 q.push(a[i]);
30 f[a[i]] = x+1; //在上一步的基础上加1
31 }
32 if (a[i] == k)
33 return ;
34 }
35 q.pop();
36 }
37 }
38 int main ()
39 {
40 int i;
41 int n,k;
42 while (~scanf("%d%d",&n,&k))
43 {
44 dfs(n,k);
45 printf("%d\n",f[k]-1); //减去农夫本来在的位置那一步
46 }
47 return 0;
48 }