洛谷春季营（对我来说是集中营一样的生活）
在打完codeforces后与大佬交流中得知，原来洛谷也有网课，于是冒着风险报了一下，感觉洛谷里的老师也是非常nice，看到我得好友，_sys，大佬，下面是oi提高组里面的一道题，
错了后改了好长时间，才完成，呜呜呜，我好菜，被中学生虐
hdu1043
八数码的问题，当时直播好多种解法，我和老师讲的不太一样，也是网上大多数人的解法，康托展开+bfs
废话少说吧，上代码
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
typedef struct nn
{
char way; //记录操作
int fath; //记录父节点,用于记录路径
}node1;
typedef struct nod
{
int aa[10];
int n; //n为9在aa中的位置
int son; //记录aa的康拓展开式
}node2;
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}},fac[10];
node1 Node[370000];//节点
void set_fac()//计算0到8的阶层
{
fac[0]=1;
for(int i=1;i<=8;i++)
fac[i]=fac[i-1]*i;
}
int cantor(int aa[])//康托展开，掌握康拓展开的方法
{
int ans=0;
for(int i=0;i<9;i++)
{
int k=0;
for(int j=i+1;j<9;j++)
if(aa[i]>aa[j])
k++;
ans+=k*fac[8-i]; //i点以后比aa[i]小的数的个数*((n-i)-1)! 之和
}
return ans;
}
void bfs(int a[])
{
queue<node2>Q;
node2 now,next;
for(int i=0;i<9;i++) now.aa[i]=a[i];
now.n=8;now.son=0;
Node[now.son].fath=0; //把最终父节点记为0，也就是本身
Q.push(now);
while(!Q.empty())
{
now=Q.front(); Q.pop();
for(int k=0;k<4;k++)
{
next=now;
int tx=now.n/3+dir[k][0];
int ty=now.n%3+dir[k][1];
if(ty>=0&&tx>=0&&ty<3&&tx<3)
{
next.n=tx*3+ty; //得到移动后x的位置
int tem=next.aa[next.n]; //得到移动后该位置的原数字
next.aa[next.n]=next.aa[now.n];
next.aa[now.n]=tem; //将两个位置上的数字交换
next.son=cantor(next.aa);
if(Node[next.son].fath==-1) //为－1时表示这个点没有访问过，那么放入队列
{
Node[next.son].fath=now.son; //当前节点的父节点就是上一个节点
if(k==0)Node[next.son].way=‘l‘;//一定要注意了，k=0是向右走，但我们是从终止状态往回搜，所以直接记录相反的方向
if(k==1)Node[next.son].way=‘r‘;
if(k==2)Node[next.son].way=‘u‘;
if(k==3)Node[next.son].way=‘d‘;
Q.push(next);
}
}
}
}
}
int main(){
int i,j,s,ss[10],a[10];
for(i=0;i<9;i++)//目标状态
a[i]=i+1; //建立目标一维矩阵，把x看成9
for(i=0;i<370000;i++)
Node[i].fath=-1;
set_fac(); //计算阶层
bfs(a); //将从最终状态能够延伸出去的所有状态以及对应路径提前打表记录
char str[50];
while(gets(str))
{
for(i=0,j=0;str[i]!=‘\0‘;i++)//把字符串变成数子
{
if(str[i]==‘x‘)
ss[j++]=9; //把x变为数子9
else if(str[i]>=‘0‘&&str[i]<=‘8‘)
ss[j++]=str[i]-‘0‘;
}
s=cantor(ss); //算出初态康托值
if(Node[s].fath==-1) {printf("unsolvable\n");continue;} //不能变成目标,因为当从起点开始搜索的时候，fath表示搜索到某
//点时，上一个点的状态，所以，如果s.fath==-1时，表示这个矩阵根本就延伸不出去，不可能达到目标状态
while(s!=0)
{
printf("%c",Node[s].way);
s=Node[s].fath;
}
printf("\n");
}
}
原文：https://www.cnblogs.com/ssxzwwsjz/p/12222707.html