题干如下:

农夫知道一头牛的位置,想要抓住它。农夫和牛都位于数轴上,农夫起始位于点N(0<=N<=100000),牛位于点K(0<=K<=100000)。农夫有两种移动方式:

  • 从X移动到X-1或X+1,每次移动花费一分钟
  • 从X移动到2*X,每次移动花费一分钟

假设牛没有意识到农夫的行动,站在原地不动。农夫最少要花多少时间才能抓住牛?

输入:

两个整数,N和K

输出:

一个整数,农夫抓到牛所要花费的最小分钟数

样例输入:

1
5 17

样例输出:

1
4

解题思路: 广度优先搜索

代码如下:

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
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int n,k;
const int Max = 100000;
int visited[Max];
struct Node
{
int x; //位置
int step; //层级
Node(int xx,int s):x(xx),step(s){}
};

queue<Node>q;

int main()
{
cin >> n >> k;
memset(visited,0,sizeof(visited)); //初始化
q.push(Node(n,0));
visited[n]=1; //出发点加入队列并标记

while(!q.empty()){
Node front = q.front();
if(front.x == k){ //如果满足要求 输出层级(分钟数)
cout<<front.step<<endl; //Prints:4
return 0;
}else{ //如果可扩展 将扩展点加入队列
if(front.x-1 >= 0 && !visited[front.x-1]){
q.push(Node(front.x-1,front.step+1));
visited[front.x-1] = 1;
}

if(front.x+1 <= Max && !visited[front.x+1]){
q.push(Node(front.x+1,front.step+1));
visited[front.x+1] = 1;
}

if(front.x*2 <= Max && !visited[front.x*2]){
q.push(Node(front.x*2,front.step+1));
visited[front.x*2] = 1;
}
q.pop();//弹出该节点
}
}
return 0;
}