宽搜。
1 #include <iostream> 2 #include <stdio.h> 3 #include <queue> 4 #include <string> 5 #include <string.h> 6 using namespace std; 7 int n,k; 8 int step[100000+10]; 9 void bfs(int begin) 10 { 11 int t,t1,t2,t3; 12 queue<int>haha; 13 haha.push(begin); 14 step[begin]=0; 15 if(begin==k) 16 return; 17 while(haha.size()>0) 18 { 19 t=haha.front(); 20 haha.pop(); 21 t1=t+1; 22 t2=t*2; 23 t3=t-1; 24 if(t1>=0&&t1<=100000+40&&step[t]+1<step[t1]) 25 { 26 step[t1]=step[t]+1; 27 haha.push(t1); 28 } 29 if(t2>=0&&t2<=100000+40&&step[t]+1<step[t2]) 30 { 31 step[t2]=step[t]+1; 32 haha.push(t2); 33 } 34 if(t3>=0&&t3<=100000+40&&step[t]+1<step[t3]) 35 { 36 step[t3]=step[t]+1; 37 haha.push(t3); 38 } 39 if(t1==k||t2==k) 40 break; 41 } 42 return ; 43 } 44 int main() 45 { 46 while(~scanf("%d%d",&n,&k)) 47 { 48 for(int i=0;i<=100000+40;++i) 49 step[i]=10000000; 50 bfs(n); 51 printf("%d\n",step[k]); 52 } 53 return 0; 54 } 55 56 57