1022 魔法数字 bfs 剪枝
2022/7/2 23:25:09
本文主要是介绍1022 魔法数字 bfs 剪枝,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
链接:https://ac.nowcoder.com/acm/contest/23156/1022
来源:牛客网
题目描述
牛妹给牛牛写了一个数字n,然后又给自己写了一个数字m,她希望牛牛能执行最少的操作将他的数字转化成自己的。操作共有三种,如下:
1.在当前数字的基础上加一,如:4转化为5
2.在当前数字的基础上减一,如:4转化为3
3.将当前数字变成它的平方,如:4转化为16
返回最少需要的操作数。 示例1
输入
复制3,10
返回值
复制2
备注:
(1≤n,m≤1000)(1\leq n,m\leq1000)(1≤n,m≤1000)
分析
不知道为啥,刚拿到这题,我完全不知道怎么优化,只知道bfs。。。。
然后看了雨巨的知道如果当前数大于2 *m - n 就不用判断了,因为m - n 就和它需要的操作次数相等
如果m<n 只要减就完事了
然后我还是过不了,才知道要加个vis。
然后不知道为啥一直过不了。。。原来是我把if(vis[t.x])提得太前面导致数组越界了。。呆滞。
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param n int整型 表示牛牛的数字
* @param m int整型 表示牛妹的数字
* @return int整型
*/
struct Q {
int x,step;
};
queue<Q>q;
int st,ed;
int vis[10000];
int bfs() {
q.push({st,0});
memset(vis,0,sizeof vis);
while(q.size()) {
auto t = q.front();q.pop();
if(t.x >= 2030) continue;
if(vis[t.x]) continue;
if(t.x == ed)return t.step;
int a = t.x - 1;int b = t.x + 1,c = t.x * t.x;
q.push({t.x - 1,t.step + 1});
q.push({t.x + 1,t.step + 1});
q.push({t.x * t.x,t.step + 1});
vis[t.x] = true;
}
return 0;
}
int solve(int n, int m) {
// write code here
st = n,ed = m;
if(m <= n) return n - m;
int x = bfs();
return x;
}
};
这篇关于1022 魔法数字 bfs 剪枝的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署