洛谷 P1379 八数码难题 解题报告
2024-08-27 03:53:48
P1379 八数码难题
题目描述
在3×3的棋盘上,摆有八个棋子,每个棋子上标有1至8的某一数字。棋盘中留有一个空格,空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是:给出一种初始布局(初始状态)和目标布局(为了使题目简单,设目标状态为123804765),找到一种最少步骤的移动方法,实现从初始布局到目标布局的转变。
输入输出格式
输入格式:
输入初始状态,一行九个数字,空格用0表示
输出格式:
只有一行,该行只有一个数字,表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)
虽然这个题没有用到,但还是提一下有解性判断
当棋盘长度是奇数时,有解等价于初始状态与目标状态的抽出来横着放的序列中逆序对个数的奇偶性相同
正常的解题思路:
用康托展开判重,用曼哈顿距离估价搜索
然而我最开始打的记搜wa的不行
最后终于想明白,有环记搜个锤子啊!!!
事实上状态量很少,直接广搜就可以
Code:
#include <cstdio>
#include <cstring>
const int N=1e6;
int s[10],fac[10],step[N],used[N],l,r;
int a[10]={0,2,3,4,9,1,5,8,7,6};
void add(int x){while(x<=9) ++s[x],x+=x&-x;}
int ask(int x){int su=0;while(x) su+=s[x],x-=x&-x;return su;}
struct node
{
int a[10];
}q[N];
int kanton(node x)
{
int ans=0;memset(s,0,sizeof(s));
for(int i=1;i<=9;i++)
ans+=fac[9-i]*(x.a[i]-1-ask(x.a[i])),add(x.a[i]);
return ans;
}
void swap(int &x,int &y){int tmp=x;x=y,y=tmp;}
int main()
{
fac[0]=1;node s;
for(int i=1;i<=9;i++) fac[i]=fac[i-1]*i,s.a[i]=a[i];
int to=kanton(s);
char c[10];scanf("%s",c+1);
for(int i=1;i<=9;i++) s.a[i]=c[i]-'0'+1;
q[0]=s;step[0]=0;
while(l<=r)
{
node now=q[l++];
int id=kanton(now),pos;
if(id==to) {printf("%d\n",step[l-1]);break;}
if(used[id]) continue;used[id]=1;
for(int i=1;i<=9;i++) if(now.a[i]==1) {pos=i;break;}
if(pos%3!=1)
{
node t=now;
swap(t.a[pos],t.a[pos-1]);
q[++r]=t,step[r]=step[l-1]+1;
}
if(pos%3)
{
node t=now;
swap(t.a[pos],t.a[pos+1]);
q[++r]=t,step[r]=step[l-1]+1;
}
if(pos>3)
{
node t=now;
swap(t.a[pos],t.a[pos-3]);
q[++r]=t,step[r]=step[l-1]+1;
}
if(pos<7)
{
node t=now;
swap(t.a[pos],t.a[pos+3]);
q[++r]=t,step[r]=step[l-1]+1;
}
}
return 0;
}
2018.8.30
最新文章
- Servlet中使用Log4j2
- Metasploit是一款开源的安全漏洞检测工具,
- rank 和 星星评级
- C语言知识整理(1):简介
- JDBC接口规范
- delphi xe6 打开andoridGPS设置
- MouseOver/MouseOut vs MouseEnter/MouseLeave
- LAN路由
- 安装和配置Symfony
- java界面--WePush-master 项目跑起来 -碰到的问题
- 关于WinCC OA
- [转]phpredis中文手册
- 基于cifar10实现卷积神经网络图像识别
- 数组和List以指定的方式拼接成字符串类型
- python中str函数isdigit、isdecimal、isnumeric的区别
- 【PAT】B1070 结绳(25 分)
- AFNetworking 源码解析
- 自定义View之圆形水波扩散动效
- Java基础第一节.Java简介
- python学习笔记之split()方法与with