3.抓住那头牛(简单搜索 BFS)

抓住那头牛

↑ 题目链接

题目

农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点 \(N\) ，牛位于点 \(K\)。农夫有两种移动方式：从 \(X\) 移动到 \(X−1\) 或 \(X+1\) ，每次移动花费一分钟从 \(X\) 移动到 \(2∗X\)，每次移动花费一分钟假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？

输入格式

共一行，包含两个整数 \(N\) 和 \(K\)。

输出格式

输出一个整数，表示抓到牛所花费的最少时间。

数据范围

\(0≤N,K≤10^5\)

输入样例：

5 17

输出样例：

4

思路

\(BFS\) 搜索即可，每次扩展题目里的三种状态，注意不要越界

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int d[N];
int n,k;

int bfs()
{
    memset(d,-1,sizeof d);
	queue<int>q;
	d[n]=0;
	q.push(n);

	while(q.size())
	{
		int t=q.front();
		q.pop();
		
		if(t==k)return d[t];
		if(t+1<N&&d[t+1]==-1)
		{
			d[t+1]=d[t]+1;
			q.push(t+1);
		}
		if(t-1>=0&&d[t-1]==-1)
		{
			d[t-1]=d[t]+1;
			q.push(t-1);
		}
		if(t*2<N&&d[t*2]==-1)
		{
			d[t*2]=d[t]+1;
			q.push(t*2);
		}
	}
}
int main()
{
	cin>>n>>k;
	
	cout<<bfs()<<endl;
	
	return 0;	
}