解题思路：简单宽搜，关键是剪枝。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<queue> 5 using namespace std; 6 const int maxn = 100005; 7 int vis[maxn]; //标记这个点是否走过 8 int n, k; 9 10 11 struct node{ 12 int x, cnt; 13 }p, now; 14 15 queue<node> q; 16 17 int bfs(int x, int cnt) 18 { 19 memset(vis, 0, sizeof(vis)); //初始化为没走过 20 while(!q.empty()) q.pop(); 21 p.x = x, p.cnt = cnt; 22 q.push(p); 23 24 while(!q.empty()) 25 { 26 p = q.front(); 27 q.pop(); 28 29 if(p.x == k) return p.cnt; //走到该点，直接返回步数 30 31 now.x = p.x + 1, now.cnt = p.cnt + 1; 32 if(now.x <= 100000 && !vis[now.x]) //关键剪枝，没走过并且在符合题目的数据范围之内 33 { 34 vis[now.x] = 1; //标记为已经走过 35 q.push(now); 36 } 37 38 now.x = p.x - 1, now.cnt = p.cnt + 1; 39 if(now.x >= 0 && !vis[now.x]) 40 { 41 vis[now.x] = 1; 42 q.push(now); 43 } 44 45 now.x = 2 * p.x, now.cnt = p.cnt + 1; 46 if(now.x <= 100000 && !vis[now.x]) 47 { 48 vis[now.x] = 1; 49 q.push(now); 50 } 51 } 52 return -1; //不会走到这一步 53 } 54 55 int main() 56 { 57 while(~scanf("%d %d", &n, &k)) 58 { 59 int ans = bfs(n, 0); 60 printf("%d ", ans); 61 } 62 return 0; 63 }