当前位置:网站首页>ACM模板笔记:八数码问题——使用BFS+康托展开打表解决
ACM模板笔记:八数码问题——使用BFS+康托展开打表解决
2022-08-10 20:51:00 【Dhaa_Ryan】
淦宁佬,能拿到蓝桥杯省二就算成功:(,ACM拿锤子奖,我这说唱专业的说唱学生百分百白给,是这样的
这只是我个人的备忘录,因为这个是刚学,所以给的注解比较详细 ,如果你能看得懂就将就看:P,实在不行去洛谷,那里大佬多的一批。
题目链接:http://poj.org/problem?id=1077
学习借鉴链接:https://www.cnblogs.com/zufezzt/p/5659276.html
判断八数码是否有解的一种方法:http://blog.sina.com.cn/s/blog_5d09995201019kjo.html
这个代码大致和之前的类似,但是按我的语法命名和数据输入习惯去改了下
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
//用来存状态
char situcation[1000];
//用来存阶乘
int c[10];
//方向
int dir[4][2] = {
{
-1,0},{
1,0},{
0,-1},{
0,1} };
//道路
string path="durl";
//检查是否遍历过
bool visit[400000];
struct Node{
int s, pos;//数字化状态和位置
Node() {
}
Node(int S, int P) {
s = S, pos = P; }
};
//记录路径
struct Path{
int fa, dir;//记录上级和上级的相对方向
}pa[400000];
//获得每一步的康托蛤希
int getnum(){
int res = 0;
for (int i = 0; situcation[i]; i++)
for (int j = i + 1; situcation[j]; j++)
if (situcation[j] < situcation[i]) res = res + c[8 - i];
return res;
}
//把数字状态转化为字符串
void getstr(int val){
int tmp[10], flag[10];
memset(flag, 0, sizeof flag);
for (int i = 0; i < 9; i++) {
tmp[i] = val / c[8 - i];
val = val % c[8 - i];
}
for (int i = 0; i < 9; i++){
int num = 0;
for (int j = 0; j < 9; j++){
if (flag[j] == 0)
num++;
if (num == tmp[i] + 1){
situcation[i] = j + '0' + 1;
if (situcation[i] == '9')
situcation[i] = 'x';
flag[j] = 1; break;
}
}
}
}
//提前进行打表
void pre() {
queue<Node>Q;
Q.push(Node(0, 8));
visit[0] = 1; pa[0].fa = -1, pa[0].dir = -1;
while (!Q.empty()){
Node h = Q.front(); Q.pop();
int a = h.pos / 3, b = h.pos % 3;
//将取出的点转化为一个字符串化状态
getstr(h.s);
for (int i = 0; i < 4; i++){
//开始进行遍历
int x = a + dir[i][0], y = b + dir[i][1];
//检测范围
if (!(x >= 0 && x <= 2 && y >= 0 && y <= 2)) continue;
//交换
int newpos = 3 * x + y;
swap(situcation[newpos], situcation[h.pos]);
int news = getnum();
//如果遍历过了就回退状态
if (visit[news]) {
swap(situcation[newpos], situcation[h.pos]);
continue;
}
//记录它的上级
pa[news].fa = h.s;
//这玩意是用来记录来的方向的
pa[news].dir = i;
//记录是否遍历过
visit[news] = 1;
//记录这个转态
Q.push(Node(news, newpos));
//进行回退,在进行下一次遍历
swap(situcation[newpos], situcation[h.pos]);
}
}
}
int main() {
c[0] = 1;
for (int i = 1; i <= 8; i++)
c[i] = c[i - 1] * i;
//打表,方便后面进行康托展开
pre();
char op; int counter = 0;
while (cin>>op){
situcation[counter++] = op;
}
int state = getnum();
//输出
if (visit[state] == 0) printf("unsolvable\n");
else {
while (1){
if (pa[state].fa == -1) break;
printf("%c", path[pa[state].dir]);
state = pa[state].fa;
}
printf("\n");
}
}
边栏推荐
- Kubernetes 笔记 / 入门 / 生产环境 / 用部署工具安装 Kubernetes / 用 kubeadm 启动集群 / 用 kubeadm 创建集群
- mysql服务器参数设置
- [mysql] 深入分析MySQL版本控制MVCC规则
- paddle 35 paddledetection保存训练过程中的log信息
- C 语言 时间函数使用技巧(汇总)
- 将视图模型转换为使用 Hilt 依赖注入
- 测试开发【Mock 平台】08 开发:项目管理(四)编辑功能和Component抽离
- 详叙c中的分支与循环
- npm warn config global `--global`, `--local` are deprecated. use `--location=global` instead.
- 数字化转型:如何引导创新领导者
猜你喜欢
Single-click to cancel the function
单选点击可取消功能
Detailed explanation and use of each module of ansible
paddle 35 paddledetection保存训练过程中的log信息
找的笔试题的复盘(一)
Web3中值得关注的基础设施
Date picker component (restrict year to set only displayed months)
win10 xbox录屏功能不能录声音怎么办
OPPO Enco X2 迎来秋季产品升级 旗舰体验全面拉满
突破次元壁垒,让身边的玩偶手办在屏幕上动起来!
随机推荐
A fullGC problem troubleshooting caused by groovy
MySQL数据库的主从复制部署详解
Apache DolphinScheduler 3.0.0 正式版发布!
优雅退出在Golang中的实现
Kyligence 通过 SOC 2 Type II 审计,以可信赖的企业级产品服务全球客户
B. Codeforces Subsequences
这些mysql基础命令、基础知识还记得吗?(面试,学习,复习都可以)一万三千字总结
2021 CybricsCTF
【图像分类】2018-MobileNetV2
2019河北省大学生程序设计竞赛部分题题解
一次由groovy引起的fullGC问题排查
Kerberos认证
社区分享|货拉拉通过JumpServer纳管大规模云上资产
【CMU博士论文】视频多模态学习:探索模型和任务复杂性,152页pdf
【网络通信四】ping工具源码cmake工程编译以及运行说明
图扑智慧电力可视化大屏,赋能虚拟电厂精准减碳
Web3中值得关注的基础设施
LeetCode questions 1-10
PostgreSQL 介绍
Single-click to cancel the function