正常情况下是可以<0,或者>k,但是会超时,因此做两个优化
-
k 直接特判,因为只能一步一步走回来
- <0 直接剪枝
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
int n,k;
int f[100004];
int op(int i,int a)
{
if(i==0) return a-1;
if(i==1) return a+1;
if(i==2) return a*2;
}
void bfs()
{
if(n>k) {
f[k] = n-k;
return ;
}
queue<int> q;
q.push(n);
while(q.size())
{
int tmp = q.front();
q.pop();
for(int i=0;i<3;i++)
{
int tx = op(i,tmp);
if(tx>=0&& tx<=k+1&&f[tx]==0 )
{
f[tx] = f[tmp]+1;
if(tx ==k) return;
q.push(tx);
}
}
}
}
int main(){
cin>>n>>k;
bfs();
cout<<f[k];
return 0;
}