$$\color{Purple}{kuangbin题解目录}$$
描述
农夫知道一头牛的位置,想要抓住它。
农夫和牛都位于数轴上,农夫起始位于点 $N$,牛位于点 $K$。
农夫有两种移动方式:
- 从 $X$ 移动到 $X-1$ 或 $X+1$,每次移动花费一分钟
- 从 $X$ 移动到 $2\*X$,每次移动花费一分钟
假设牛没有意识到农夫的行动,站在原地不动。
农夫最少要花多少时间才能抓住牛?
输入格式
共一行,包含两个整数$N$和$K$。
输出格式
输出一个整数,表示抓到牛所花费的最少时间。
数据范围
$0 \\le N,K \\le 10^5$
输入样例:
5 17
输出样例:
4
思路
经典bfs,一维搜索,此处可不用判断农夫与牛的位置关系.
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define MAXN 100010
using namespace std;
struct node{
int pos;
int step;
};
node start_,end_;
int vis[MAXN];
int dir[3]={-1,1,2};
int bfs()
{
queue<node> q;
q.push(start_);
vis[start_.pos]=1;
while(q.size()>0)
{
node temp=q.front();
q.pop();
if(temp.pos==end_.pos)
return temp.step;
for(int i=0;i<=2;i++)
{
int dx;
if(dir[i]==2)
dx=temp.pos*2;
else dx=temp.pos+dir[i];
if(dx>=0&&dx<=100000&&vis[dx]==0)
{
vis[dx]=1;
q.push({dx,temp.step+1});
}
}
}
return -1;
}
int main()
{
scanf("%d %d",&start_.pos,&end_.pos);
printf("%d\n",bfs());
return 0;
}