农夫知道一头牛的位置,想要抓住它。
农夫和牛都位于数轴上,农夫起始位于点 N,牛位于点 K。
农夫有两种移动方式:
假设牛没有意识到农夫的行动,站在原地不动。
农夫最少要花多少时间才能抓住牛?
输入格式
共一行,包含两个整数N和K。
输出格式
输出一个整数,表示抓到牛所花费的最少时间。
数据范围
输入样例:
5 17
输出样例:
4
BFS,老水题了,还是一维的。。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
#define x first
#define y second
typedef pair<int,int> pii;
int n,k,vis[N];
void bfs(int x){
queue<pii>q;
q.push({x,0});
while(!q.empty()){
auto now=q.front();
vis[now.x]=1;
q.pop();
if(now.x==k){
cout<<now.y<<endl;
return;
}
if(now.x+1<=100000&&!vis[now.x+1]){
vis[now.x+1]=1;
q.push({now.x+1,now.y+1});
}
if(now.x-1>=0&&!vis[now.x-1]){
vis[now.x-1]=1;
q.push({now.x-1,now.y+1});
}
if(now.x*2<=100000&&!vis[now.x*2]){
vis[now.x*2]=1;
q.push({now.x*2,now.y+1});
}
}
}
int main(){
cin>>n>>k;
bfs(n);
return 0;
}