题目描述
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?
输入
Line 1: Two space-separated integers: N and K
输出
Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.
示例输入
5 17
示例输出
4
广度优先搜索练习
1 #include<stdio.h>
2 #include<
string.h>
3 #include<iostream>
4 #include<queue>
5 using namespace std;
6
7 int vis[
100100];
8 struct node
9 {
10 int date;
11 int step;
12 };
13 int bfs(
int s,
int t)
14 {
15 queue<node>
que;
16 struct node tmp,ans;
17 int tx;
18 ans.date =
s;
19 ans.step =
0;
20 que.push(ans);
21 vis[s] =
1;
22 while(!
que.empty())
23 {
24 tmp =
que.front();
25 que.pop();
26 tx = tmp.date-
1;
27 if(tx <
0 || tx >
100000);
28 else if(!
vis[tx])
29 {
30 vis[tx] =
1;
31 ans.date =
tx;
32 ans.step = tmp.step+
1;
33 que.push(ans);
34 if(ans.date ==
t)
35 return ans.step;
36 }
37 tx = tmp.date+
1;
38 if(tx <
0 || tx >
100000);
39 else if(!
vis[tx])
40 {
41 vis[tx] =
1;
42 ans.date =
tx;
43 ans.step = tmp.step+
1;
44 que.push(ans);
45 if(ans.date ==
t)
46 return ans.step;
47 }
48 tx = tmp.date*
2;
49 if(tx <
0 || tx >
100000);
50 else if(!
vis[tx])
51 {
52 vis[tx] =
1;
53 ans.date =
tx;
54 ans.step = tmp.step+
1;
55 que.push(ans);
56 if(ans.date ==
t)
57 return ans.step;
58 }
59 }
60 }
61
62 int main()
63 {
64 int s,t;
65 scanf(
"%d %d",&s,&
t);
66 if(s ==
t)
67 {
68 printf(
"0\n");
69 }
70 else
71 {
72 memset(vis,
0,
sizeof(vis));
73 printf(
"%d\n",bfs(s,t));
74 }
75 return 0;
76 }
View Code
转载于:https://www.cnblogs.com/LK1994/p/3191733.html
