BFS专题1 数字操作

原创于 2023-07-31 22:28:36 发布 · 粉丝可见 · 109 阅读 · 0 · 0 · 本内容遵循CC 4.0 BY-SA版权协议版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/132031520

题目：

样例：

7

4

思路：

BFS宽度搜索，操作只有 +1 和 x 2 这两个操作，所以我们可以看成操作时一个二叉树

从图中，我们可以看出，在操作的过程中难免会有一些重复操作，所以我们也要用一个bool数组来标记，尽量避免重复操作，其次对应的层数就是我们操作的次数，所以我们输出对应的层数即可。

代码详解如下：

#include <iostream>
#include <queue>
using namespace std;
const int N = 1e9 + 10;

// vis 用来标记操作得到过的结果数值
bool vis[N];
// n 为操作目标数值
int n;

// u 为 根节点
int BFS(int u)
{
	// BFS 用队列的先进先出的特性
	// 达到宽度搜索，每层搜索的效果
	queue<int>q;

	q.push(u);	//	存入根节点

	int step = 0;	// step 表示操作步数

	while (q.size())
	{
		// q.size() 的大小表示这一层有多少个结点
		int k = q.size();

		while (k--)
		{
			// k 表示我们这一层可以操作多少个结点

			// num 表示当前节点数值
			int num = q.front();
			q.pop();

			if (num == n)
			{
				// 如果操作达到目标数值
				// 返回该层数，也就是返回该步数
				return step;
			}

			if (num + 1 <= n && !vis[num + 1])
			{
				// 如果 当前操作没有操作过
				// 并且是小于等于我们的目标操作值
				// 那么我们可以统计好这次操作结果
				// 并做好标记
				q.push(num + 1);
				vis[num + 1] = true;
			}
			if (num * 2 <= n && !vis[num * 2])
			{
				// 如果 当前操作没有操作过
				// 并且是小于等于我们的目标操作值
				// 那么我们可以统计好这次操作结果
				// 并做好标记
				q.push(num * 2);
				vis[num * 2] = true;
			}
		}
		step++;		// 操作次数累加，层数累加
	}
	return -1;		// 如果没有，我们也返回个 -1 来防止层序错误吧
}

int main()
{
	cin >> n;
	int ans = BFS(1);
	cout <<  ans << endl;
	return 0;
}