[Luogu] 八数码难题
2024-09-06 15:09:19
https://www.luogu.org/problemnew/show/P1379
long long ago
暴力bfs
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <queue>
#include <cstring>
#include <string> using namespace std;
const string s_end = ""; struct Node {
string s;
int step;
};
queue <Node> Q1;
map <string, bool> mp;
string s_start;
int Step; inline void pd(string ss, int answer) {
if(ss == s_end) {
printf("%d",answer);
exit();
}
} inline void bfs() {
while(!Q1.empty()) {
Node topp = Q1.front();
Q1.pop();
string s1 = topp.s;
Step = topp.step;
int f = s1.find('');
Node nxt;
if(f == ) {
swap(s1[], s1[]);
pd(s1, topp.step + );
if(!mp[s1]) {
nxt.s = s1;
nxt.step = topp.step + ;
Q1.push(nxt);
mp[s1] = ;
}
swap(s1[], s1[]);
swap(s1[], s1[]);
pd(s1, topp.step + );
if(!mp[s1]) {
nxt.s = s1;
nxt.step = topp.step + ;
Q1.push(nxt);
mp[s1] = ;
}
continue;
}
if(f == ) {
swap(s1[], s1[]);
pd(s1, topp.step + );
if(!mp[s1]) {
nxt.s = s1;
nxt.step = topp.step + ;
Q1.push(nxt);
mp[s1] = ;
}
swap(s1[], s1[]);
swap(s1[], s1[]);
pd(s1, topp.step + );
if(!mp[s1]) {
nxt.s = s1;
nxt.step = topp.step + ;
Q1.push(nxt);
mp[s1] = ;
}
swap(s1[], s1[]);
swap(s1[], s1[]);
pd(s1, topp.step + );
if(!mp[s1]) {
nxt.s = s1;
nxt.step = topp.step + ;
Q1.push(nxt);
mp[s1] = ;
}
continue;
}
if(f == ) {
swap(s1[], s1[]);
pd(s1, topp.step + );
if(!mp[s1]) {
nxt.s = s1;
nxt.step = topp.step + ;
Q1.push(nxt);
mp[s1] = ;
}
swap(s1[], s1[]);
swap(s1[], s1[]);
pd(s1, topp.step + );
if(!mp[s1]) {
nxt.s = s1;
nxt.step = topp.step + ;
Q1.push(nxt);
mp[s1] = ;
}
continue;
}
if(f == ) {
swap(s1[], s1[]);
pd(s1, topp.step + );
if(!mp[s1]) {
nxt.s = s1;
nxt.step = topp.step + ;
Q1.push(nxt);
mp[s1] = ;
}
swap(s1[], s1[]);
swap(s1[], s1[]);
pd(s1, topp.step + );
if(!mp[s1]) {
nxt.s = s1;
nxt.step = topp.step + ;
Q1.push(nxt);
mp[s1] = ;
}
swap(s1[], s1[]);
swap(s1[], s1[]);
pd(s1, topp.step + );
if(!mp[s1]) {
nxt.s = s1;
nxt.step = topp.step + ;
Q1.push(nxt);
mp[s1] = ;
}
continue;
}
if(f == ) {
swap(s1[], s1[]);
pd(s1, topp.step + );
if(!mp[s1]) {
nxt.s = s1;
nxt.step = topp.step + ;
Q1.push(nxt);
mp[s1] = ;
}
swap(s1[], s1[]);
swap(s1[], s1[]);
pd(s1, topp.step + );
if(!mp[s1]) {
nxt.s = s1;
nxt.step = topp.step + ;
Q1.push(nxt);
mp[s1] = ;
}
swap(s1[], s1[]);
swap(s1[], s1[]);
pd(s1, topp.step + );
if(!mp[s1]) {
nxt.s = s1;
nxt.step = topp.step + ;
Q1.push(nxt);
mp[s1] = ;
}
swap(s1[], s1[]);
swap(s1[], s1[]);
pd(s1, topp.step + );
if(!mp[s1]) {
nxt.s = s1;
nxt.step = topp.step + ;
Q1.push(nxt);
mp[s1] = ;
}
continue;
}
if(f == ) {
swap(s1[], s1[]);
pd(s1, topp.step + );
if(!mp[s1]) {
nxt.s = s1;
nxt.step = topp.step + ;
Q1.push(nxt);
mp[s1] = ;
}
swap(s1[], s1[]);
swap(s1[], s1[]);
pd(s1, topp.step + );
if(!mp[s1]) {
nxt.s = s1;
nxt.step = topp.step + ;
Q1.push(nxt);
mp[s1] = ;
}
swap(s1[], s1[]);
swap(s1[], s1[]);
pd(s1, topp.step + );
if(!mp[s1]) {
nxt.s = s1;
nxt.step = topp.step + ;
Q1.push(nxt);
mp[s1] = ;
}
continue;
}
if(f == ) {
swap(s1[], s1[]);
pd(s1, topp.step + );
if(!mp[s1]) {
nxt.s = s1;
nxt.step = topp.step + ;
Q1.push(nxt);
mp[s1] = ;
}
swap(s1[], s1[]);
swap(s1[], s1[]);
pd(s1, topp.step + );
if(!mp[s1]) {
nxt.s = s1;
nxt.step = topp.step + ;
Q1.push(nxt);
mp[s1] = ;
}
continue;
}
if(f == ) {
//4 7 6 7 8 7
swap(s1[], s1[]);
pd(s1, topp.step + );
if(!mp[s1]) {
nxt.s = s1;
nxt.step = topp.step + ;
Q1.push(nxt);
mp[s1] = ;
}
swap(s1[], s1[]);
swap(s1[], s1[]);
pd(s1, topp.step + );
if(!mp[s1]) {
nxt.s = s1;
nxt.step = topp.step + ;
Q1.push(nxt);
mp[s1] = ;
}
swap(s1[], s1[]);
swap(s1[], s1[]);
pd(s1, topp.step + );
if(!mp[s1]) {
nxt.s = s1;
nxt.step = topp.step + ;
Q1.push(nxt);
mp[s1] = ;
}
continue;
}
if(f == ) {
//58 78
swap(s1[], s1[]);
pd(s1, topp.step + );
if(!mp[s1]) {
nxt.s = s1;
nxt.step = topp.step + ;
Q1.push(nxt);
mp[s1] = ;
}
swap(s1[], s1[]);
swap(s1[], s1[]);
pd(s1, topp.step + );
if(!mp[s1]) {
nxt.s = s1;
nxt.step = topp.step + ;
Q1.push(nxt);
mp[s1] = ;
}
continue;
}
}
} int main() {
cin >> s_start;
Node now;
now.s = s_start;
now.step = ;
Q1.push(now);
bfs();
return ;
}
//
最新文章
- CSS3外轮廓属性
- setValue和setObject的区别
- android xml 布局错误（黑掉了）Missing styles. Is the correct theme chosen for this layout?
- 用SugarORM快速开发需要同步和保存大量数据的Android互联网客户端
- DBLINK的session无法关闭，报异常！
- ios 键盘弹起
- codevs 3269 混合背包
- js截取字符串区分汉字字母代码
- redis学习研究--Redis作者谈Redis应用场景
- 【HTTP 2】简介（Introduction）
- Kattis - Fenwick Tree(树状数组区间更新单点求值）
- 细说MyEclipse调试
- 新版Azure Automation Account 浅析（二） --- 更新Powershell模块和创建Runbook
- 阿里云免费购买SSL证书，nginx无缝升级https
- arcgis for js 根据多边形自动缩放
- IntelliJ IDEA 和 Pycharm 破解
- IIS+NGINX 负载web服务器
- 使用Oozie中workflow的定时任务重跑hive数仓表的历史分期调度
- python-flask-session和scoped_session区别
- 一,ESP8266下载和刷固件(基于Lua脚本语言)
热门文章
- RHadoop: REDUCE capability required is more than the supported max container capability in the cluster
- 『Python基础』第4节：基础数据类型初识
- CentOS 7.X 静默安装Oracle 12C数据库
- Angularjs 中 ng-repeat 循环绑定事件
- 彻底弄懂HTTP缓存机制及原理-转载
- Computer Vision_18_Image Stitching： Image Alignment and Stitching——2006
- 库克谈新iPhone不支持5G的理由，学习一下如何高手怎么应答
- python爬虫伪装技术应用
- python 2.7安装pygame报错解决办法pygame-1.9.4-cp27-cp27m-win_amd64.whl is not a supported wheel on this platform.
- linux实操_shell系统函数