AcWing 1100. 抓住那头牛
原题链接
简单
作者:
mkuiwu
,
2021-02-10 19:06:45
,
所有人可见
,
阅读 305
#include<iostream>
#include<cstring>
using namespace std;
const int N = 2 * 1e5 + 10;
int n, k;
int st[N], q[N];
int bfs(){
memset(st, -1, sizeof st);
q[0] = n;
int hh = 0, tt = 0;
st[n] = 0;
while(hh <= tt){
int t = q[hh ++];
if(t == k) return st[t];
// 2. 分步走, 会保证每个点会被算一次 且 只算一次
if(t + 1 < N && st[t+1] == -1){
q[++ tt] = t + 1;
st[t+1] = st[t] + 1;
}
if(t - 1 >= 0 && st[t-1] == -1) {
q[++ tt] = t - 1;
st[t - 1] = st[t] + 1;
}
if(t * 2 < N && st[t*2] == -1){
q[++ tt] = t * 2;
st[t*2] = st[t] + 1;
}
}
}
int main(){
cin >> n >> k;
cout << bfs() << endl;
return 0;
}