Catch That Cow (广度优先搜索）

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超时，但其实题目里根本就没有用到，这也算是学习心得了把，嘿嘿嘿。
直接上代码：

#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 6 3
2 15 4
3 4 1
19 54 8
16 25 5
4 86 7
65 21 44

最后

以上就是忧郁超短裙为你收集整理的Catch That Cow (广度优先搜索）的全部内容，希望文章能够帮你解决Catch That Cow (广度优先搜索）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。