[ZJOI2005]九数码游戏

[ZJOI2005]九数码游戏

题目描述

[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");
}
}

上一篇:[CVPR 2016] Weakly Supervised Deep Detection Networks论文笔记


下一篇:JS几种数组遍历方式总结