AcWing 1100. 抓住那头牛 BFS
农夫知道一头牛的位置，想要抓住它。
农夫和牛都位于数轴上，农夫起始位于点 N，牛位于点 K。
农夫有两种移动方式：
- 从 X 移动到 X−1或 X+1，每次移动花费一分钟
- 从 X 移动到 2X，每次移动花费一分钟
假设牛没有意识到农夫的行动，站在原地不动。
农夫最少要花多少时间才能抓住牛？
输入格式
共一行，包含两个整数N和K。
输出格式
输出一个整数，表示抓到牛所花费的最少时间。
数据范围
0\leq N, K\leq 10^5
输入样例：
5 17输出样例：
4BFS,老水题了，还是一维的。。
#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;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021/02/15 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
