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.
挺簡(jiǎn)單的廣搜，不知道哪里錯(cuò)了，wa了近20遍，悲劇，可能是邊界沒(méi)處理好
1
#include<stdio.h>
2#include<string.h>
3#include<math.h>
4#define inf 100000
5#define MAX 1000000
6int n,k,ans;
7long long q[MAX+1],number[inf+1];
8short flag[inf+1];
9int bfs()
10
{
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
{
20 head++;
21 now=q[head];
22 if (now==k)
23 {
24 return number[now]-1;
25
}
26 now1=now-1;
27 if (now1>=0&&now1<=inf&&!flag[now1])
28 {
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 {
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 {
45 tail++;
46 q[tail]=now1;
47 flag[now1]=1;
48 number[now1]=number[now]+1;
49 }
50 }
51
}
52int main()
53{
54 while (scanf("%d%d",&n,&k)!=EOF)
55 {
56 if(n==k)
57 {
58 printf("0\n");
59 continue;
60 }
61 if (k==0)
62 {
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
75