洛谷—— P1379 八数码难题
2024-09-29 20:38:45
https://daniu.luogu.org/problem/show?pid=1379
题目描述
在3×3的棋盘上,摆有八个棋子,每个棋子上标有1至8的某一数字。棋盘中留有一个空格,空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是:给出一种初始布局(初始状态)和目标布局(为了使题目简单,设目标状态为123804765),找到一种最少步骤的移动方法,实现从初始布局到目标布局的转变。
输入输出格式
输入格式:
输入初始状态,一行九个数字,空格用0表示
输出格式:
只有一行,该行只有一个数字,表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)
输入输出样例
输入样例#1:
283104765
输出样例#1:
4 BFS搜索每种移动的状态,hash判重
#include <cstring>
#include <cstdio>
#include <queue> #define swap(a,b) {int tmp=a; a=b; b=tmp; }
const int op[][]={{,,},
{,,},
{,,}};
bool vis[];
struct Checkerboard {
int step;
int map[][];
Checkerboard() { step=; memset(map,,sizeof(map)); }
} u;
std::queue<Checkerboard>que;
int fx[]={,,,-};
int fy[]={,,-,};
char s[]; inline bool print(Checkerboard x)
{
for(int i=; i<; ++i)
for(int j=; j<; ++j)
if(x.map[i][j]!=op[i][j]) return ;
return true;
}
inline int BFS()
{
que.push(u);
for(Checkerboard v; !que.empty(); )
{
v=u=que.front(); que.pop();
int tmp=,t=,k=;
for(int i=; i<; ++i)
for(int j=; j<; ++j)
tmp+=k*u.map[i][j],t++,k*=t;
vis[tmp]=;
if(print(u)) return u.step; int x,y;
for(int i=; i<; ++i)
for(int j=; j<; ++j)
if(u.map[i][j]==)
{
for(int k=; k<; ++k)
{
x=fx[k]+i,y=fy[k]+j;
if(x>=&&y>=&&x<&&y<)
{
v.map[i][j]=v.map[x][y];
v.map[x][y]=;
v.step=u.step+;
int tmp=,t=,k=;
for(int i=; i<; ++i)
for(int j=; j<; ++j)
tmp+=k*v.map[i][j],t++,k*=t;
if(!vis[tmp])
vis[tmp]=,que.push(v);
v=u;
}
}
goto STEP;
}
STEP:;
}
return ;
} int Presist()
{
scanf("%s",s);
for(int i=; i<; ++i) u.map[][i]=s[i]-'';
for(int i=; i<; ++i) u.map[][i%]=s[i]-'';
for(int i=; i<; ++i) u.map[][i%]=s[i]-'';
printf("%d\n",BFS());
return ;
} int Aptal=Presist();
int main(){;}
最新文章
- mysql在linux下的安装
- 修改linux文件权限命令:chmod(转)
- OC中的私有变量和description
- OLTP与OLAP的介绍
- oracle 10g 学习之函数和存储过程(12)
- webstorm激活码
- hadoop2.2编程: 重写comparactor
- 201521123053 《Java程序设计》第5周学习总结
- curl命令用于模拟http浏览器发起动作
- C++内存机制中内存溢出、内存泄露、内存越界和栈溢出的区别和联系
- Oracle设置主键自增
- #个人博客作业Week3——必应词典案例分析
- ARIMA模型识别、计算p、q值
- bootstrap代码(一)
- java分模块项目在idea中使用maven打包失败(ps:maven常用到的命令)
- git实践:对比svn
- mobiscroll的例子
- <;只看这个就够了。。。>;Android自动化测试及性能优化
- MySQL学习【第七篇索引管理及执行计划】
- 封装你的协程Unity TaskManager