当前位置:网站首页>AcWing 4300. Two operations (minimum number of BFS searches)
AcWing 4300. Two operations (minimum number of BFS searches)
2022-07-06 22:56:00 【GHOSTANDBREAD】
Given a positive integer nn, We hope you can through a series of operations , Change it to another positive integer mm.
There are two kinds of operations :
- Multiply the current number by 22.
- Subtract... From the current number 11.
requirement , During the transformation , The number is always positive .
Please calculate , The minimum number of operations required .
Input format
a line , Two different positive integers nn and mm.
Output format
An integer , Indicates the minimum number of operations required .
Data range
front 66 Test points meet 1≤n,m≤101≤n,m≤10.
All test points meet 1≤n,m≤100001≤n,m≤10000.
sample input 1:
4 6
sample output 1:
2
sample input 2:
10 1
sample output 2:
9
The code is as follows :
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
int n, m;
struct point{
int x;
int step=0;
};
queue<point> r;
int vis[200010];
int main()
{
ios::sync_with_stdio(false);
cout.tie(NULL);
memset(vis, 0, sizeof(vis));
cin >> n >> m;
point start;
start.x = n;
start.step = 0;
vis[n] = 1;
r.push(start);
while(!r.empty())
{
int xx = r.front().x;
if(xx == m){
cout<< r.front().step;
break;
}
for(int i = 0; i < 2; i ++)
{
int y;
if(i == 0 && xx < m) y = 2 * xx;
else{
y = xx - 1;
if(y <= 0){
continue;
}
}
if(vis[y] == 0){
point temp;
temp.x = y;
temp.step = r.front().step + 1;
vis[y] = 1;
r.push(temp);
}
}
r.pop();
}
return 0;
}
边栏推荐
- 【踩坑合辑】Attempting to deserialize object on CUDA device+buff/cache占用过高+pad_sequence
- DR-Net: dual-rotation network with feature map enhancement for medical image segmentation
- Signed and unsigned keywords
- UVa 11732 – strcmp() Anyone?
- Uniapp setting background image effect demo (sorting)
- mysql查看表结构的三种方法总结
- 案例推荐丨安擎携手伙伴,保障“智慧法院”更加高效
- uniapp设置背景图效果demo(整理)
- How to confirm the storage mode of the current system by program?
- POJ 1258 Agri-Net
猜你喜欢
CocosCreator+TypeScripts自己写一个对象池
Rust knowledge mind map XMIND
Hard core observation 545 50 years ago, Apollo 15 made a feather landing experiment on the moon
Improving Multimodal Accuracy Through Modality Pre-training and Attention
浅谈网络安全之文件上传
Motion capture for snake motion analysis and snake robot development
[compilation principle] LR (0) analyzer half done
Unified Focal loss: Generalising Dice and cross entropy-based losses to handle class imbalanced medi
ACL 2022 | small sample ner of sequence annotation: dual tower Bert model integrating tag semantics
MySQL authentication bypass vulnerability (cve-2012-2122)
随机推荐
Method of canceling automatic watermarking of uploaded pictures by CSDN
MySQL教程的天花板,收藏好,慢慢看
Detailed explanation of ThreadLocal
UVa 11732 – strcmp() Anyone?
Signed and unsigned keywords
DockerMySQL无法被宿主机访问的问题解决
[compilation principle] LR (0) analyzer half done
Financial professionals must read book series 6: equity investment (based on the outline and framework of the CFA exam)
Slide the uniapp to a certain height and fix an element to the top effect demo (organize)
Comparison between variable and "zero value"
Hard core observation 545 50 years ago, Apollo 15 made a feather landing experiment on the moon
OpenNMS separation database
Sword finger offer question brushing record 1
Aardio - integrate variable values into a string of text through variable names
MATLAB小技巧(27)灰色预测
Redis 持久化机制
Machine test question 1
Puppeteer连接已有Chrome浏览器
How to confirm the storage mode of the current system by program?
Chapter 19 using work queue manager (2)