[ZJOI2005]九数码游戏
题目描述
输入输出格式
输入格式：
输入文件中包含三行三列九个数，同行的相邻两数用空格隔开，表示初始状态每个方格上的数字。初始状态不会是目标状态。
输出格式：
如果目标状态无法达到，则输出“UNSOLVABLE”（引号不输出）。
否则，第一行是一个整数S，表示最少的操作次数。接下来4 × (S + 1)行，每四行表示一个状态：前三行每行三个整数，相邻两数用空格隔开，表示每个方格上的数字，第四行是一个空行，作为分隔。第一个状态必须是初始状态，最后一个状态必须是目标状态。
输入输出样例
输入样例#1：
2 3 0
1 8 7
5 4 6
输出样例#1：
4
2 3 0
1 8 7
5 4 6 1 2 3
5 8 0
4 6 7 1 2 3
0 5 8
4 6 7 0 1 2
4 5 3
6 7 8 0 1 2
3 4 5
6 7 8 因为这是3*3的全排列矩阵变换；
最多有9！（362880）种状态；
用BFS，搜到终点为止，中间记录一下路径；
将3*3的全排列映射成一一对应的数，可以用康托展开；
最好不要用map，可能会超时；
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std; int a[],q[],st,ed,b[],f[],ge,ans;
int c[],hash[];
int fac[]={,,,,,,,,}; int calc1()
{
int i,j,t,sum;
sum=;
for(i=;i<;i++)
{
t=;
for(j=i+;j<;j++)
if(a[i]>a[j])
++t;
sum+=t*fac[-i-];
}
return sum+;
} int calc()
{
int i,j,t,sum;
sum=;
for(i=;i<;i++)
{
t=;
for(j=i+;j<;j++)
if(b[i]>b[j])
++t;
sum+=t*fac[-i-];
}
return sum+;
} void fen(int x)
{
int i,j,t,vst[]={};
x--;
for(i=;i<;i++)
{
t=x/fac[-i-];
for(j=;j<;j++)
if(!vst[j])
{
if(t==) break;
--t;
}
b[i]=j;
vst[j]=;
x%=fac[-i-];
}
} int main()
{
int x=;
for(int i=;i<=;i++)
for(int j=;j<=;j++){
scanf("%d",&a[(i-)*+j-]);
}
x=calc1();
ge=;
if(x==ge){
printf("");
return ;
}
q[]=x;
hash[x]=-;
st=; ed=;
while(st<ed){
int x=q[++st];
fen(x);
for(int i=;i<;i++)
f[i]=b[i];
b[]=f[];
b[]=f[];
b[]=f[];
int y=calc();
if(hash[y]==){
hash[y]=x;
ed++;
q[ed]=y;
}
if(y==ge)
break;
b[]=f[];
b[]=f[];
b[]=f[]; b[]=f[];
b[]=f[];
b[]=f[];
b[]=f[];
b[]=f[];
b[]=f[];
b[]=f[];
b[]=f[]; y=calc();
if(hash[y]==){
hash[y]=x;
ed++;
q[ed]=y;
}
if(y==ge)
break;
}
x=hash[ge];
if(x==){
printf("UNSOLVABLE\n");
return ;
}
while(x!=-){
ans++;
c[ans]=x;
x=hash[x];
}
printf("%d\n",ans);
for(int i=ans;i>;i--){
fen(c[i]);
printf("%d %d %d\n",b[],b[],b[]);
printf("%d %d %d\n",b[],b[],b[]);
printf("%d %d %d\n",b[],b[],b[]);
printf("\n");
}
if(ans>=){
printf("0 1 2\n");
printf("3 4 5\n");
printf("6 7 8\n");
}
}