Note: This article is available in Chinese only. 本文暂无英文版本。
View original
做过一道类似的题
因为是问最短，很容易想到是bfs
对于点x，可以到达点x-1,和点2*x
需要注意的是上界限。
并不是max(m,n)
因为可能先达到比m大，之后再减回来的情况是更优的。
max(2m,2n)肯定是足够的
1/*************************************************************************
2 > File Name: code/cf/#295/B.cpp
3 > Author: 111qqz
4 > Email: rkz2013@126.com
5 > Created Time: 2015年08月17日 星期一 04时16分51秒
6 ************************************************************************/
7
8#include<iostream>
9#include<iomanip>
10#include<cstdio>
11#include<algorithm>
12#include<cmath>
13#include<cstring>
14#include<string>
15#include<map>
16#include<set>
17#include<queue>
18#include<vector>
19#include<stack>
20#define y0 abc111qqz
21#define y1 hust111qqz
22#define yn hez111qqz
23#define j1 cute111qqz
24#define tm crazy111qqz
25#define lr dying111qqz
26using namespace std;
27#define REP(i, n) for (int i=0;i<int(n);++i)
28typedef long long LL;
29typedef unsigned long long ULL;
30const int inf = 0x7fffffff;
31const int N=1E4+7;
32int n,m;
33int d[N];
34int mx;
35
36void bfs()
37{
38 memset(d,-1,sizeof(d));
39 d[n] = 0 ;
40 queue<int>q;
41 q.push(n);
42 while (!q.empty())
43 {
44 int px = q.front();q.pop();
45 if (px==m)
46 {
47 cout<<d[m]<<endl;
48 return;
49 }
50
51 int nxt[2];
52 nxt[0] = px - 1;
53 nxt[1] = 2*px;
54 for ( int i = 0 ; i < 2 ; i++)
55 {
56 if (nxt[i]>=1&&nxt[i]<=mx&&d[nxt[i]]==-1)
57 {
58 d[nxt[i]] = d[px] + 1;
59 q.push(nxt[i]);
60 }
61 }
62 }
63}
64int main()
65{
66 scanf("%d %d",&n,&m);
67 mx = max(n,m);
68 bfs();
69
70
71return 0;
72}