首页 > 极客资料 博客日记
剪枝的应用,bfs判重 蚱蜢跳——蓝桥p642
2024-09-27 19:00:03极客资料围观18次
本篇文章分享剪枝的应用,bfs判重 蚱蜢跳——蓝桥p642,对你有帮助的话记得收藏一下,看极客之家收获更多编程知识
问题描述
总共有九个盘子,八只蚱蜢,且每个盘子中只能容下一只蚱蜢,蚱蜢的编号为1~8,如果蚱蜢所在的盘子紧邻着空盘子,那么该蚱蜢可以从自己的盘子跳到空盘子中,也可以隔一个盘子跳到空盘子中,问一开始状态是012345678,蚱蜢至少该跳多少步才可以被变为087654321
输入
无
输出
蚱蜢跳过的步数
问题分析:
- 题目中说的是蚱蜢在跳,但蚱蜢有很多只,这会增加编码难度,但空盘子只有一个,我们可以让盘子移动,你那么就可以规避这个问题
- 经过分析,盘子的移动方式有四种,左1,左2,右1,右2,但由于题目中这些盘子是一个圈,所以在移动时也要考虑这一因素,也就时我们常说的化曲为直,多提一句,这个移动其实是有公式的但是我不大像推,所以就用了switch语句,效果是一样的
- 之后就是本题的核心-————去重,这里我使用的时map,其实还有set,去重操作可以帮助删去大量的重复节点
#include<iostream>
#include<map>
#include<queue>
using namespace std;
struct node {
node(){}
node(string ss, int tt,int po) :s(ss),t(tt),pos(po){}
string s;
int t; //表示步数
int pos; //表示当前字符串0的位置,从0开始数
};
map<string, bool>mp;
queue<node>que;
node now, nxt;
int cal(int i,int pos) {
switch (i) {
case 1:
return pos + 1 > 8 ? pos+1-8-1 : pos + 1;
break;
case 2:
return pos + 2 > 8 ? pos+2-8-1 : pos + 2;
break;
case 3:
return pos - 1 < 0 ? pos-1+8+1 : pos - 1;
break;
case 4:
return pos - 2 < 0 ? pos-2+8+1 : pos - 2;
}
}
void bfs() {
while (!que.empty()) {
now = que.front();
que.pop();
//如果找到答案就结束循环
if (now.s == "087654321") {
cout << now.t << endl;
break;
}
for (int i = 1; i <= 4; i++) {
int k = cal(i, now.pos);
nxt.pos = k;
nxt.s = now.s;
nxt.t = now.t + 1;
char tmp = nxt.s[now.pos];
nxt.s[now.pos] = nxt.s[k];
nxt.s[k] = tmp;
//map判重
if (!mp[nxt.s]) {
mp[nxt.s] = true;
que.push(nxt);
}
}
}
}
int main() {
string s = "012345678";
que.push(node(s, 0, 0));
mp[s] = true;
bfs();
return 0;
}
版权声明:本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若内容造成侵权/违法违规/事实不符,请联系邮箱:jacktools123@163.com进行投诉反馈,一经查实,立即删除!
标签:
相关文章
最新发布
- Nuxt.js 应用中的 prerender:routes 事件钩子详解
- 【问题解决】Tomcat由低于8版本升级到高版本使用Tomcat自带连接池报错无法找到表空间的问题
- 【FAQ】HarmonyOS SDK 闭源开放能力 —Vision Kit
- 六、Spring Boot集成Spring Security之前后分离认证流程最佳方案
- 《JVM第7课》堆区
- .NET 8 高性能跨平台图像处理库 ImageSharp
- 还在为慢速数据传输苦恼?Linux 零拷贝技术来帮你!
- 刚毕业,去做边缘业务,还有救吗?
- 如何避免 HttpClient 丢失请求头:通过 HttpRequestMessage 解决并优化
- 让性能提升56%的Vue3.5响应式重构之“版本计数”