Q博士的太空电梯 (bfs)

20:55:01

题目描述

公元9012年，q博士发明了一部太空电梯，与一般电梯不同，太空电梯不能直接到达目点。太空电梯只有上升和下降两个按键，如果电梯上升，
它只能上升当前高度的距离；如果下降，它一次只能下降1米的距离。
为了使大家都能上太空去玩耍，q博士想请你根据电梯的工作原理，计算到达目的点最少需要按几次按键

输入

多组输入

每组输入有两个数n和m（1<=n,m<=10^7),表示当前高度n和目的点m

输出

输出计算结果

样例输入

4 6
10 1
255 999999

样例输出

2
9
28
题意：电梯有两个按钮 ， 一个是上升目前高度的按钮 ， 另一个是下降1个高度的按钮。
如何从起始高度到达目标高度并要求求出按最少次按钮的次数。

我一开始想的是用dfs，我就去看了下分别在什么情况下使用dfs和bfs。
dfs特点：可以不重不漏的枚举所有可以到达目标状态的路径。（回溯思想 ， 枚举思想）

bfs特点：效率较高，适合于找一条最快到达目标状态的路径。（发散思想）

 1 #include <iostream>;
 2 #include <stdio.h>;
 3 #include <queue>;
 4 #include <string.h>;
 5 #include <vector>
 6 #include <algorithm>
 7 #include <math.h>
 8 #include <stack>
 9 using namespace std;
10 int n , m, vis[1000000] , v[1000000] ;//vis标记查过的点，防止影响结果和效率。 v记录每条路径的目前的按按钮的次数。
11 
12 void bfs(int n)
13 {
14     queue<int>q;
15     if(n < m)
16     {
17         q.push(n);
18         vis[n] = 0 ;
19         v[n] = 1 ;
20         if(m % 2 == 1) 
21         {
22             m += 1;
23             vis[n] += 1 ;
24         }
25         while(!q.empty())
26         {
27             int a = q.front();
28             q.pop();
29             if(a != 0 && a * 2 <= m &&!v[a * 2]) // 一开始没加 a * 2 < m 该条件 ， 发现数据一大就会爆。
30             {
31             vis[2 * a] = vis[a] + 1 ;
32             v[a * 2] = 1 ;
33             q.push(2 * a);
34             }
35             if(a - 1 >= 0 && !v[a - 1])
36             {
37                 vis[a - 1] = vis[a] + 1 ;
38                 v[a - 1] = 1 ;
39                 q.push(a - 1);
40             }
41             if(a == m)
42             {
43                 cout << vis[m] << endl ;
44                 break ;
45             }
46         }
47     }
48     else
49     {
50         cout << n - m << endl ;
51     }
52 }
53 
54 void init()
55 {
56     memset(v , 0 , sizeof(v));
57     memset(vis , 0 , sizeof(vis));
58 }
59 
60 
61 int main()
62 {
63     while(cin >> n >> m)
64     {
65          init();
66          bfs(n);
67 
68     }
69     return 0 ;
70 }

 

刷题后感：标记查找过的点是bfs 和 dfs 的重要部分。