BFS练习_1（C++板块提升计划）【含代码讲解】

zhangjinxuan

题目描述

给你一个数字a，每次可以选择下面四种操作中的一种：

1.把数字a加上一。
2.把数字a乘以2。
3.把数字a乘以3。
4.把数字a减去一。

问把这个a变成b最少需要多少步。

你要回答q个询问，b1,b2,…,bq，输出把a变成b1,b2,…,bq的最小步数。

输入描述

第一行两个整数a,q。

接下来一行q个整数b1,…,bq。

输出描述

输出q个数字，分别表示把a变成b1,b2…,bq的最小步数;

样例输入

1. 3 10
   
2. 1 2 3 4 5 6 7 8 9 10

复制代码

样例输出

1. 2 1 0 1 2 1 2 2 1 2

复制代码

数据规模
对于所有数据，保证1≤a,q,bi≤100000。
测试链接
评论区公布

这道题很有意思，希望大家独立思考完成

现在，上讲解！

讲解
0.1 ： 想一想思路（1)：
一开始，大家的思路应该都是这样的：

写一个函数，每个询问BFS一下就可以了！

但是我们想一想时间复杂度，每一次询问最坏就是O(n), 共q次询问，在这十的五次方这种级别，根本过不了！

这肯定不是正解，大家稍安勿躁，现在介绍第二种方法。

0.2 想一想思路（2):
经过观察，我们发现，一开始的数，他总是固定的，所以，我们可以干什么呢？

我们可不可以在一开始就从一开始的数开始，把所有数都BFS好，然后，每一次询问，不就是O（1)了吗？

这肯定是正解，时间复杂度O(n),一定能过，那我们开始写代码吧！（如果你不明白是什么意思，后面的代码会体会到的）

1. 基本框架：

1. #include <cstdio>
   
2. 
   
3. using namespace std;
   
4. 
   
5. int main() {
   
6.         return 0;
   
7. }

复制代码

太煎蛋（简单）了，不说

2.定义变量：

1. 
   
2. int a, q, x, step[30001], queue[300001], front = 1, rear = 0;
   
3. 
   
4. #define MAXN 300001

复制代码

a代表一开始的数，q代表询问次数，step_i表示从a变到i所要的次数（step必须开3e5+1，后面会体会到的），queue是BFS必须要有的东西，front和rear就是队首队尾。
而MAXN，就是这个数最大变成多少，这个数只要大于300000，不会溢出就可以了。

3.声明BFS函数:

1. void init();

复制代码

3.1 ：定义BFS函数，并写出基本的框架：

1. queue[++rear] = a;
   
2. while (rear + 1 != front) {
   
3.         ...
   
4. }

复制代码

首先，a肯定要入队，然后在队列非空的情况下将更多的元素入队

3.2：将遍历到的数字加入队列（重点）：

1.                 int front_n = queue[front++];
   
2.                 int new_n = front_n + 1;
   
3.                 if (new_n != a && step[new_n] == 0 && new_n <= MAXN) {
   
4.                         step[new_n] = step[front_n] + 1;
   
5.                         queue[++rear] = new_n;
   
6.                 }
   
7.                 new_n = front_n * 2;
   
8.                 if (new_n != a && step[new_n] == 0 && new_n <= MAXN) {
   
9.                         step[new_n] = step[front_n] + 1;
   
10.                         queue[++rear] = new_n;
    
11.                 }
    
12.                 new_n = front_n * 3;
    
13.                 if (new_n != a && step[new_n] == 0 && new_n <= MAXN) {
    
14.                         step[new_n] = step[front_n] + 1;
    
15.                         queue[++rear] = new_n;
    
16.                 }
    
17.                 new_n = front_n - 1;
    
18.                 if (new_n != a && step[new_n] == 0 && new_n <= MAXN && new_n >= 0) {
    
19.                         step[new_n] = step[front_n] + 1;
    
20.                         queue[++rear] = new_n;
    
21.                 }

复制代码

首先，获取队首元素，然后出队，接着获取新的元素，接着我们首先要判断新元素不等于a的情况并且之前没有遍历过（就是看step_n是不是0，是则遍历过），还要看看是否小于最大值（不然会遍历int范围所有数了，会超时）
注意，最后一个操作要特判，因为可能有<0的情况，这样就溢出了。

倒回去说一遍：step要开3e5+1的原因，因为new_n可能是3e5,如果只开1e5,那么：

1. step[new_n] == 0

复制代码

就溢出了

重点是这里：

1. step[new_n] = step[front_n] + 1;
   
2. queue[++rear] = new_n;

复制代码

第一步，更新答案step,他要等于 他原本是什么变来的元素 所需的步数 加一（挺长的，尽量理解），然后加入队列

4.main：

1. scanf("%d%d", &a, &q);
   
2. init();
   
3. while (q--) {
   
4.         scanf("%d", &x);
   
5.         printf("%d ", step[x]);
   
6. }

复制代码

输入，再调用刚刚我们写的函数初始化答案，接着执行q次，输入x，输出step_x

5.完整参考代码：

1. #include <cstdio>
   
2. 
   
3. using namespace std;
   
4. 
   
5. int a, q, x, step[300001], queue[300001], front = 1, rear = 0;
   
6. 
   
7. #define MAXN 100001
   
8. 
   
9. void init() {
   
10.         queue[++rear] = a;
    
11.         while (rear + 1 != front) {
    
12.                 int front_n = queue[front++];
    
13.                 int new_n = front_n + 1;
    
14.                 if (new_n != a && step[new_n] == 0 && new_n <= MAXN) {
    
15.                         step[new_n] = step[front_n] + 1;
    
16.                         queue[++rear] = new_n;
    
17.                 }
    
18.                 new_n = front_n * 2;
    
19.                 if (new_n != a && step[new_n] == 0 && new_n <= MAXN) {
    
20.                         step[new_n] = step[front_n] + 1;
    
21.                         queue[++rear] = new_n;
    
22.                 }
    
23.                 new_n = front_n * 3;
    
24.                 if (new_n != a && step[new_n] == 0 && new_n <= MAXN) {
    
25.                         step[new_n] = step[front_n] + 1;
    
26.                         queue[++rear] = new_n;
    
27.                 }
    
28.                 new_n = front_n - 1;
    
29.                 if (new_n != a && step[new_n] == 0 && new_n <= MAXN && new_n >= 0) {
    
30.                         step[new_n] = step[front_n] + 1;
    
31.                         queue[++rear] = new_n;
    
32.                 }
    
33.         }
    
34. }
    
35. int main() {
    
36.         scanf("%d%d", &a, &q);
    
37.         init();
    
38.         while (q--) {
    
39.                 scanf("%d", &x);
    
40.                 printf("%d ", step[x]);
    
41.         }
    
42.         return 0;
    
43. }

复制代码

总结：这个题还是挺有意思的，方法挺有意思，但是关键是你要想出来

[如果喜欢，别忘了小小的评分，一个荣誉也是爱]

zhangjinxuan

测试链接：http://oj.daimayuan.top/problem/147

zhangjinxuan

@高山 @不二如是
求支持

zhangjinxuan

来个进阶要求：变的过程不能有4（数位不能有4),不能变出来输出-1

高山

支持！！！

zhangjinxuan

高山 发表于 2022-10-2 12:01
支持！！！

感谢支持

zhangjinxuan

怎么这么冷清，求大家支持@元豪