康托展开(魔板)
看题解没有什么人用cantor写,于是乎用了个contor写了个题》0《。
首先cantor展开是根据全排列的原理,对每一个排列编辑一个序号,因为排列是唯一的,因此序号也一定唯一。故可以达到状态压缩的目的。那怎么计算cantor展开值呢?
对于每一个序列,我们都能知道如果当前位置后面有多少个比他大(或者小)的数,那么可以知道他在原排列的位置处于第多少个序列,而这个第多少个就是我们要求的cantor展开值!!!
看列子:1 3 2 4 5
这个展开值 = (后面大于当前位置的数) * (当前位置的阶乘)
原列子为:1! * 4 + 2! * 2 + 3! * 2 + 4! * 1 + 5! * 0 = 4 + 4 + 12 + 24 = 44,故1 3 2 4 5这个序列在1 2 3 4 5这个序列的后44个。
由于题目只有8个数字,因此可以预先处理阶乘可以8!=40320,总状态数最多为40320
时间复杂度为4032087 = 2257920,可以看出来是非常快速的,只需要100ms不到就可以跑完
上代码!!!
#include "bits/stdc++.h"
using namespace std;
int step[10],vis[40400];
char pre[40400] = "\0";
struct node{
char s[9];
int p;
int k;
};
void init()
{
step[0] = 1;
for(int i = 1;i <= 9;i ++) step[i] = i * step[i - 1];
}
int cantor(char s[])
{
int res = 0;
for(int i = 0;i < 8;i ++){
int cnt = 0;
for(int j = i + 1;j < 8;j ++)
if(s[j] < s[i]) cnt ++;
res += step[8 - i - 1] * cnt;
}
return res;
}
void moveA(char s[])
{
swap(s[7],s[0]);
swap(s[6],s[1]);
swap(s[5],s[2]);
swap(s[4],s[3]);
}
void moveB(char s[])
{
swap(s[0],s[3]);
swap(s[4],s[7]);
swap(s[3],s[1]);
swap(s[4],s[6]);
swap(s[3],s[2]);
swap(s[4],s[5]);
}
void moveC(char s[])
{
swap(s[1],s[2]);
swap(s[5],s[6]);
swap(s[1],s[5]);
}
void bfs(char s[])
{
int mi=INT_MAX,tmp,ed,res;
node p1,p2,p3;
char s1[9] = "12345678";
queue <node> que;
node st = {"",0,0};
strcpy(st.s,s1);
res = cantor(s);
pre[0] = '*';
que.push(st);
while(!que.empty()) {
node v = que.front();
que.pop();
if(v.k == res){
mi = v.p;
break;
}
p1 = p2 = p3 = v;
moveA(p1.s);
tmp = cantor(p1.s);
if(!pre[tmp]) {
p1.p = v.p + 1;
p1.k = tmp;
que.push(p1);
pre[tmp] = 'A';
vis[tmp] = v.k;
}
moveB(p2.s);
tmp = cantor(p2.s);
if(!pre[tmp]) {
p2.p = v.p + 1;
p2.k = tmp;
que.push(p2);
pre[tmp] = 'B';
vis[tmp] = v.k;
}
moveC(p3.s);
tmp = cantor(p3.s);
if(!pre[tmp]) {
p3.p = v.p + 1;
p3.k = tmp;
que.push(p3);
pre[tmp] = 'C';
vis[tmp] = v.k;
}
}
string ans="";
if(mi){
printf("%d\n",mi);
while(pre[res] != '*'){
ans += pre[res];
res = vis[res];
}
reverse(ans.begin(),ans.end());
printf("%s\n",ans.c_str());
}
else puts("0");
}
int main()
{
char s[10];
int x;
init();
for(int i = 0;i < 8;i ++) {
scanf("%d",&x);
s[i] = x + '0';
}
bfs(s);
return 0;
}