欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Q博士的太空电梯 (bfs)

程序员文章站 2022-03-19 23:37:21
20:55:01 题目描述 公元9012年,Q博士发明了一部太空电梯,与一般电梯不同,太空电梯不能直接到达目点。太空电梯只有上升和下降两个按键,如果电梯上升, 它只能上升当前高度的距离;如果下降,它一次只能下降1米的距离。 为了使大家都能上太空去玩耍,Q博士想请你根据电梯的工作原理,计算到达目的点最 ......

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 的重要部分。