问题描述
农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点N(0<=N<=100000)，牛位于点K(0<=K<=100000)。农夫有两种移动方式：
从X移动到X-1或X+1，每次移动花费一分钟从X移动到2*X，每次移动花费一分钟
假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？
输入 两个整数，N和K
输出 一个整数，农夫抓到牛所要花费的最小分钟数
样例
INPUT
5 17
OUTPUT
4
解题思路
BFS
dfs主要用于整个图的遍历，可以求得多个解；bfs则常用于求最短路径如本题。本题的移动方法有三种：向后一步、向前一步和传送（位置*2），则用队列存储每次行动这三种移动方法的结果，每次行动让时间+1。
完整代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <iomanip>
#include <queue>
using namespace std;
struct point{//位置和所用时间
int x;
int time;
};
queue <point> Q;
int n, k, flag[100001];//flag用于标记若曾走过则不再查询
void bfs(){
while(!Q.empty()){
point t = Q.front();//读取初始的位置t.x和所用时间t.time = 0
Q.pop();
int X = t.x;
int Time = t.time;//在循环中每次保存弹出的位置和时间
if(X == k){//找到牛
cout<<Time<<endl;
return;
}
//没找到，有三种走法，左走一步、右走一步和传送，分别分析
if(X >= 1&&!flag[X - 1]){
flag[X - 1] = 1;
point tem;
tem.x = X - 1;
tem.time = Time + 1;
Q.push(tem);//将此种走法（位置和用时）存入队列
}
if(X <= k&&!flag[X + 1]){
flag[X + 1] = 1;
point tem;
tem.x = X + 1;
tem.time = Time + 1;
Q.push(tem);
}
if(X <= k&&2*X <= 100001&&!flag[2*X]){
flag[2*X] = 1;
point tem;
tem.x = 2*X;
tem.time = Time + 1;
Q.push(tem);
}
}
}
int main(){
cin>>n>>k;
point t;
t.x = n;
t.time = 0;
Q.push(t);
bfs();
return 0;
}
参考链接：https://blog.csdn.net/qq_43746332/article/details/89930172
