AcWing 4300. $\Large\color{purple}{最小步数模型}$
原题链接
中等
作者:
Value
,
2023-05-08 21:15:47
,
所有人可见
,
阅读 91
#include <iostream>
#include <queue>
#include <unordered_set>
using namespace std;
unordered_set<int> set;
int main(){
int n, m; cin >> n >> m;
queue<int> qu;
qu.push(n);
set.insert(n);
int step = 0;
bool flag = false;
while(!qu.empty() && !flag){
int len = qu.size();
for(int k = 0; k < len; k ++ ){
int cur = qu.front();
qu.pop();
if(cur == m){
cout << step << endl;
flag = true;
break;
}
if(cur * 2 <= 20000 && set.find(cur * 2) == set.end()){
set.insert(cur * 2);
qu.push(cur * 2);
}
if(cur - 1 > 0 && set.find(cur - 1) == set.end()){
set.insert(cur - 1);
qu.push(cur - 1);
}
}
step ++ ;
}
return 0;
}