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.
这道题我打算把它加入人间迷惑行为，真的是特别迷，题目其实特别简单，就是普通的广度优先搜索，但奇怪的是有一个根本没有用的a[100001]数组，你定义了他就AC，如果不定义他就是Runtime超时，但其实题目里根本就没有用到，这也算是学习心得了把，嘿嘿嘿。
直接上代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57#include<iostream> #include<algorithm> #include<queue> using namespace std; struct node //用一个struct来记录当前的位置，和当前位置需要的步数 { int x; int step; }; int bfs(int n, int k); //广度优先搜索 int a[100001]; //完全没有作用的a数组，但是他可以保证不超时hhh int b[100001]; //用来确保位置没有走过，如果走过还要走回来，步数一定是额外的，所以用来记录 int main() { int n, k; cin >> n >> k; b[n] = 1; //确保开始位置已经走过 cout << bfs(n, k); return 0; } int bfs(int n, int k) { queue<node>q; //基本，用队列来保存 node now, next; //定义现在和下一步 now.x = n; //现在的位置是n（题目输入） now.step = 0; //现在的步数还没有走，是0 q.push(now); //入队 while (!q.empty()) //当队列不是空的时候进行不断循环 { now = q.front(); //now为队首 if (now.x == k) //如果当前位置是最后的结束位置，直接得出结果 return now.step; if (now.x > 0 && !b[now.x - 1]) //计算-1的位置 { next.x = now.x - 1; next.step = now.step + 1; b[next.x] = 1; q.push(next); } if (now.x < k && !b[now.x+1]) //计算+1的位置 { next.x = now.x + 1; next.step = now.step + 1; b[next.x] = 1; q.push(next); } if (now.x < k && !b[now.x * 2]) //计算*2的位置 { next.x = now.x * 2; next.step = now.step + 1; b[next.x] = 1; q.push(next); } q.pop(); //当这个位置遍历结束后，将其移出队列，进行下一步操作 } }
之前由于总是感觉代码是正确的，所以做了几组测试数据：
起点 终点 步数
1
2
3
4
5
6
7
81 6 3 2 15 4 3 4 1 19 54 8 16 25 5 4 86 7 65 21 44
最后
以上就是忧郁超短裙最近收集整理的关于Catch That Cow (广度优先搜索）的全部内容，更多相关Catch内容请搜索靠谱客的其他文章。
发表评论 取消回复