Codeforces Round 295 (Div. 2) B. Two Buttons （BFS）

本文主要是介绍Codeforces Round 295 (Div. 2) B. Two Buttons （BFS），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

瓦夏发现了一个奇怪的装置。装置的前面板上有一个红色按钮、一个蓝色按钮和一个显示正整数的显示屏。点击红色按钮后，设备将显示的数字乘以 $2$ 。点击蓝色按钮后，设备从显示屏上的数字中减去 $1$ 。如果某个时候数字不再是正数，设备就会崩溃。显示屏可以显示任意大的数字。最初，显示屏显示的数字为 $n$ 。

鲍勃希望在显示屏上显示数字 $m$ 。他最少要点击多少次才能得到这个结果？

输入
输入的第一行也是唯一一行包含两个不同的整数 $n$ 和 $m ( 1 ≤ n, m ≤ 10^4 )$ ，中间用空格隔开。

输出
打印一个数字–从数字 $n$ 中取出数字 $m$ 所需的最少按键次数。

这是一类问题：多个操作方式对数操作，可以使用DFS或者BFS，当然BFS更为安全，并且具有最短路的特性，所以如果不需要回溯的话就尽量使用BFS。

对于此题，只需要搜遍所有操作就可以了，但是要加上一个限制条件，即被操作后的数不能够超过1e5，如果不加限制的话就可能会导致永远搜不完了。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+10;
int n,m;
#define pii pair<int,long long>map<long long,bool>vis;void bfs(){queue<pii>q;	//first元素代表步数，second代表当前操作的数q.push({0,n});while(q.size()){auto t = q.front();q.pop();if(t.second == m){	//如果搜到了就直接输出，BFS第一次搜到的一定是最短的cout << t.first;exit(0);}//操作1if(t.second - 1 >= 0 && t.second - 1 <= 10005){if(!vis[t.second - 1]){q.push({t.first+1,t.second - 1});vis[t.second - 1] = 1;}}//操作2if(!vis[t.second*2] && t.second*2 <= 10005){q.push({t.first + 1,t.second*2});vis[t.second*2] = 1;}}
}int main(){cin >> n >> m;bfs();return 0;
}