题意:八数码,但是转移的方式是转动,一共十二种,有多组询问,初态唯一,终态不唯一。

题解:初态唯一,那么可以预处理出012345678的所有转移情况,然后将初态对012345678做一个映射,再枚举一下终态的所有情况,取最小值即可。

学了逆cantor展开,cantor展开是一个变进制数,每位上是原序列对应位置上的逆序值。那么求逆时候,就先除最大的位权得到对应位置上的逆序值,根据逆序值可以知道它在剩下的序列中第几大,然后标记它,迭代。状态转移有点麻烦。

#include<cstdio>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
//#define local const int maxn = ;
int d[maxn];
int fac[] = { ,,,,,,,,};//,362880
int St[],Ed[]; int cantor(int *e) {
int ret = ;
for(int i = ; i < ; i++) {
int cnt = ;
for(int j = i+; j < ; j++)
if(e[j] < e[i]) cnt++;
ret += fac[-i] * cnt;
}
return ret;
} void invCantor(int *a,int code)
{
bool vis[] = {};
for(int i = ; i < ; i++){
int t = code/fac[-i];
int j;
for( j = ; j < ; j++){
if(!vis[j]){
if(t == ) break;
t--;
}
}
a[i] = j; vis[j] = ;
code %= fac[-i];
}
} int dir[][] = {
{,,,,,,,,},{,,,,,,,,},{,,,,,,,,},
{,,,,,,,,},{,,,,,,,,},{,,,,,,,,},
{,,,,,,,,},{,,,,,,,,},{,,,,,,,,},
{,,,,,,,,},{,,,,,,,,},{,,,,,,,,} };
queue<int> q; void BfsPre()
{
memset(d,-,sizeof(d) );
d[] = ;
q.push();
while(q.size()){
int u = q.front();q.pop();
int tmp[];
invCantor(tmp,u);
for(int i = ; i < ; i++){
int tmp2[];
for(int j = ; j < ; j++){
tmp2[j] = tmp[dir[i][j]];
}
int v = cantor(tmp2);
if(~d[v]) continue;
d[v] = d[u]+;
q.push(v);
}
}
} int query()
{
int mp[];
for(int i = ; i < ; i++) { mp[St[i]] = i; }
bool appear[] = {};
for(int i = ; i < ; i++){
if(~Ed[i]) appear[Ed[i] = mp[Ed[i]]] = ;
}
int vec[],sz = ;
for(int i = ; i < ; i++) {
if(!appear[i]) vec[sz++] = i;
}
if(sz == ) return ;
if(sz == ) return d[cantor(Ed)];
const int INF = 0x7fffffff;
int ans = INF;
int tmp[];
do{
int j = ;
for(int i = ; i < ; i++){
if(~Ed[i]) { tmp[i] = Ed[i]; }
else { tmp[i] = vec[j++]; }
}
int Hash = cantor(tmp);
if(~d[Hash]) ans = min(ans,d[Hash]);
}while(next_permutation(vec,vec+sz));
return ans!=INF? ans : -;
} int main()
{
#ifdef local
freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
#endif // local
int T;
BfsPre(); scanf("%d",&T);
for(int k = ; k <= T; k++){
printf("Case #%d: ",k);
for(int i = ; i < ; i ++){
scanf("%d",St+i);
St[i]--;
}
getchar();
char buf[];
for(int i = ; i < ; i++){
gets(buf);
for(int j = ; j < ; j+=){
if(''<=buf[j] && buf[j] <= ''){
Ed[i*+j/] = buf[j] - '';
}else Ed[i*+j/] = -;
}
}
int ans = query();
if(~ans) printf("%d\n",ans);
else printf("No Solution!\n");
} return ;
}
05-11 17:46