Catch That Cow
Time Limit: 2000MS |
|
Memory Limit: 65536K |
Total Submissions: 27595 |
|
Accepted: 8495 |
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.
挺简单的广搜,不知道哪里错了,wa了近20遍,悲剧,可能是边界没处理好
1
#include<stdio.h>
2
#include<string.h>
3
#include<math.h>
4
#define inf 100000
5
#define MAX 1000000
6
int n,k,ans;
7
long long q[MAX+1],number[inf+1];
8
short flag[inf+1];
9
int bfs()
10![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
11
int head,tail;
12
long long now,now1;
13
head=0;
14
tail=1;
15
q[tail]=n;
16
flag[n]=1;
17
number[n]=1;
18
while(head<tail)
19![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
20
head++;
21
now=q[head];
22
if (now==k)
23![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
24
return number[now]-1;
25
}
26
now1=now-1;
27
if (now1>=0&&now1<=inf&&!flag[now1])
28![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
29
tail++;
30
q[tail]=now1;
31
flag[now1]=1;
32
number[now1]=number[now]+1;
33
}
34
now1=now+1;
35
if (now1>=0&&now1<=inf&&!flag[now1])
36![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
37
tail++;
38
q[tail]=now1;
39
flag[now1]=1;
40
number[now1]=number[now]+1;
41
}
42
now1=now*2;
43
if (now1>=0&&now1<=inf&&!flag[now1])
44![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
45
tail++;
46
q[tail]=now1;
47
flag[now1]=1;
48
number[now1]=number[now]+1;
49
}
50
}
51
}
52
int main()
53![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
54
while (scanf("%d%d",&n,&k)!=EOF)
55![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
56
if(n==k)
57![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
58
printf("0\n");
59
continue;
60
}
61
if (k==0)
62![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
63
printf("%d\n",n);
64
continue;
65
}
66
memset(q,0,sizeof(q));
67
memset(number,0,sizeof(number));
68
memset(flag,0,sizeof(flag));
69
ans=bfs();
70
printf("%d\n",ans);
71
}
72
return 0;
73
}
74![](/Images/OutliningIndicators/None.gif)
75![](/Images/OutliningIndicators/None.gif)