codeforces 520 B. Two Buttons (bfs)
做过一道类似的题
因为是问最短，很容易想到是bfs
对于点x，可以到达点x-1,和点2*x
需要注意的是上界限。
并不是max(m,n)
因为可能先达到比m大，之后再减回来的情况是更优的。
max(2m,2n)肯定是足够的
/*************************************************************************
> File Name: code/cf/#295/B.cpp
> Author: 111qqz
> Email: rkz2013@126.com
> Created Time: 2015年08月17日 星期一 04时16分51秒
************************************************************************/
1#include<iostream>
2#include<iomanip>
3#include<cstdio>
4#include<algorithm>
5#include<cmath>
6#include<cstring>
7#include<string>
8#include<map>
9#include<set>
10#include<queue>
11#include<vector>
12#include<stack>
13#define y0 abc111qqz
14#define y1 hust111qqz
15#define yn hez111qqz
16#define j1 cute111qqz
17#define tm crazy111qqz
18#define lr dying111qqz
19using namespace std;
20#define REP(i, n) for (int i=0;i<int(n);++i)
21typedef long long LL;
22typedef unsigned long long ULL;
23const int inf = 0x7fffffff;
24const int N=1E4+7;
25int n,m;
26int d[N];
27int mx;
1void bfs()
2{
3 memset(d,-1,sizeof(d));
4 d[n] = 0 ;
5 queue<int>q;
6 q.push(n);
7 while (!q.empty())
8 {
9 int px = q.front();q.pop();
10 if (px==m)
11 {
12 cout<<d[m]<<endl;
13 return;
14 }
1 int nxt[2];
2 nxt[0] = px - 1;
3 nxt[1] = 2*px;
4 for ( int i = 0 ; i < 2 ; i++)
5 {
6 if (nxt[i]>=1&&nxt[i]<=mx&&d[nxt[i]]==-1)
7 {
8 d[nxt[i]] = d[px] + 1;
9 q.push(nxt[i]);
10 }
11 }
12 }
13}
14int main()
15{
16 scanf("%d %d",&n,&m);
17 mx = max(n,m);
18 bfs();
return 0;
}