求x到y的最少计算次数 (BFS)
2024-10-20 20:50:56
时间限制:1秒
空间限制:262144K
给定两个-100到100的整数x和y,对x只能进行加1,减1,乘2操作,问最少对x进行几次操作能得到y?
例如:
a=3,b=11: 可以通过3*2*2-1,3次操作得到11;
a=5,b=8:可以通过(5-1)*2,2次操作得到8;
a=3,b=11: 可以通过3*2*2-1,3次操作得到11;
a=5,b=8:可以通过(5-1)*2,2次操作得到8;
输入描述:
输入以英文逗号分隔的两个数字,数字均在32位整数范围内。
输出描述:
输出一个数字
输入例子1:
3,11
输出例子1:
3
思路:广度优先搜索。(队列实现)
#include <iostream>
#include <queue>
#include <cstdio>
using namespace std; int main() {
int x, y;
int cnt = ;
bool flag = false;
scanf("%d,%d", &x, &y);
queue<int> q;
q.push(x);
while (!q.empty()) {
int len = q.size();
for (int i = ; i < len; i++) {
int tmp = q.front();
q.pop();
if (tmp == y) {
flag = true;
break;
} else {
q.push(tmp + );
q.push(tmp - );
q.push(tmp * );
}
}
if (flag)
break;
cnt++;
}
cout << cnt << endl;
return ;
}
#include <iostream>
#include <queue>
#include <cstdio>
using namespace std; int main() {
int x, y;
scanf("%d,%d", &x, &y);
queue<pair<int, int> > q;
pair<int, int> tmp({x, });
q.push(tmp); while (!q.empty()) {
tmp = q.front();
q.pop();
if (tmp.first == y) {
cout << tmp.second << endl;
break;
} else {
q.push({tmp.first + , tmp.second + });
q.push({tmp.first - , tmp.second + });
q.push({tmp.first * , tmp.second + });
}
}
return ;
}
最新文章
- mybatis支持属性使用驼峰的命名
- [译] AlphaGo 的确是一个大事件
- 6个好用的Web开发工具
- leetcode Pow(doubule x,int n)
- 开发设计模式(六)多例模式(Multition Pattern)
- Bag of Words/Bag of Features的Matlab源码发布
- 汉得第二次考核答案整理(通信,IO,文件等)
- [RxJS] Stopping a Stream with TakeUntil
- php正则的使用[替换,匹配]
- 杭电三部曲一、基本算法;19题 Cow Bowling
- UIImage 和 UIImageView区别
- redis3 list类型
- Tornado框架简介(二)
- Mesos源码分析(8): Mesos-Slave的初始化
- 1.python虚拟环境的安装-用以同时使用py2,py3
- GoLang学习之变量定义和初始化
- HDU 4498 Function Curve (自适应simpson)
- PHP项目收藏
- uboot 下更改NAND的分区 fdisk
- Python 高斯坐标转经纬度算法
热门文章
- php 将几个变量合为数组,变量名和值对应
- Unity3D_(插件)DOTween动画插件
- JS框架_(JQuery.js)动画效果鼠标跟随
- JS框架_(Laydate.js)简单实现日期日历
- 微信小程序_(组件)canvas画布
- sqli-labs(42)
- MySort(选做)的实现
- 菜鸟requireJS教程---2、基本知识
- 石川es6课程---3、变量let和常量const
- PHP基本语句