AcWing 1100. 抓住那头牛
原题链接
简单
作者:
十六
,
2021-01-14 11:24:16
,
所有人可见
,
阅读 199
#include<bits/stdc++.h>
using namespace std;
const int MAX = 1e5;
typedef pair<int, int> PII;
int x, y;
PII q[MAX*6];
bool v[MAX*2];
int bfs(int x){
int hh = 0, tt = 0;
q[hh] = {x, 0};
while(hh<=tt){
PII t = q[hh++];
//位置小于1e5时+1才有意义
if(t.first<MAX){
x = t.first+1;
if(x==y) return t.second+1;
else if(!v[x]) q[++tt] = {x, t.second+1}, v[x] = true;
}
//位置大于0时-1才有意义
if(t.first>0){
x = t.first-1;
if(x==y) return t.second+1;
else if(!v[x]) q[++tt] = {x, t.second+1}, v[x] = true;
}
//位置在(0, 1e5)范围内*2才有意义
if(t.first>0 && t.first<MAX){
x = t.first*2;
if(x==y) return t.second+1;
else if(!v[x]) q[++tt] = {x, t.second+1}, v[x] = true;
}
}
return -1;
}
int main(){
scanf("%d%d", &x, &y);
cout<< bfs(x)<< endl;
return 0;
}