CDOJ 485 UESTC 485 Game （八数码变形，映射，逆cantor展开）

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

题解：初态唯一，那么可以预处理出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 ;

}

巴特西

CDOJ 485 UESTC 485 Game （八数码变形，映射，逆cantor展开）

最新文章

热门文章