本文主要是介绍抓住那头牛——BFS,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
农夫知道一头牛的位置,想要抓住它。
农夫和牛都位于数轴上,农夫起始位于点 N,牛位于点 K。
农夫有两种移动方式:从 X 移动到 X−1 或 X+1,每次移动花费一分钟从 X 移动到 2∗X,每次移动花费一分钟。
假设牛没有意识到农夫的行动,站在原地不动。
农夫最少要花多少时间才能抓住牛?
输入格式
共一行,包含两个整数N和K。
输出格式
输出一个整数,表示抓到牛所花费的最少时间。
数据范围
0≤N,K≤105
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef pair<int,int> PII;
const int N=2e6+10;
int d[N];
bool vis[N];
int n,k;
queue <int> q;
int bfs(int n)
{vis[n]=1;q.push(n);while (q.size()&&!vis[k]){int x=q.front();q.pop();if (!vis[x-1]&&x-1>=0){d[x-1]=d[x]+1;q.push(x-1);vis[x-1]=1;}if (!vis[x+1]&&x+1<=2e5) {d[x+1]=d[x]+1;q.push(x+1);vis[x+1]=1;}if (!vis[2*x]&&2*x<=2e5){d[2*x]=d[x]+1;q.push(2*x);vis[2*x]=1;}}return d[k];
}
signed main()
{ios;cin>>n>>k;cout<<bfs(n);return 0;
}
这篇关于抓住那头牛——BFS的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!