[ZJOI2005]九数码游戏(BFS+hash)

Solution

这题的话直接上BFS就可以了，因为要输出方案，所以我们要开一个pre数组记录前驱，最后输出就可以了。

对于状态的记录，一般都用哈希来存，但因为这道题比较特殊，它是一个排列，所以我们可以利用康拓展开把空间压到9！。

康拓展开

一个排列的康拓展开表示的是字典序比他小的排列的个数，所以我们统计一下每一位后面有几个比它小的数字，乘上(n-i)!

inline int zx_hash(int x){

    for(int i=;i>=;--i)a[i]=x%,x/=;

    int num=;

    for(int i=;i<=;++i){

        int aa=;

        for(int j=i+;j<=;++j)if(a[i]>a[j])aa++;

        num+=aa*jie[-i];

    }

    return num;

}

逆康拓展开

我们不但要支持把排列映射成数字，还要支持把数字映射成排列。

具体操作就是从高到低按位考虑，令x=num/(n-i)!，那么可选集合中有x个数是比这一位上的数字小的，所以我们选择第x+1个数。

inline int anti_hash(int x){

   int num=;

   for(int i=;i<=;++i)vec[i]=i;int zo=;

   for(int i=;i>=;--i){

         int y=x/jie[i];

         x=x%jie[i];

         num=num*+vec[y];

         for(int j=y;j<zo;++j)vec[j]=vec[j+];zo--;

   }

 return num;

}

不过康拓展开的复杂度是n^2的，但常数较小，遇到哈希排列之类的问题试一下。

Code

#include<iostream>

#include<cstdio>

#include<queue>

#include<vector>

#include<algorithm>

#define mm make_pair

#define N 12

using namespace std;

const int r1[]={,,,,,,,,,};

const int r2[]={,,,,,,,,,};

int jie[N],a[N],d1[N],d2[N],x,win,ans[],ji[],tag,tot,vec[];

struct node{

    int first,second;

};

queue<node>q;

inline int zx_hash(int x){

    for(int i=;i>=;--i)a[i]=x%,x/=;

    int num=;

    for(int i=;i<=;++i){

        int aa=;

        for(int j=i+;j<=;++j)if(a[i]>a[j])aa++;

        num+=aa*jie[-i];

    }

    return num;

}

inline int anti_hash(int x){

   int num=;

   for(int i=;i<=;++i)vec[i]=i;int zo=;

   for(int i=;i>=;--i){

         int y=x/jie[i];

         x=x%jie[i];

         num=num*+vec[y];

         for(int j=y;j<zo;++j)vec[j]=vec[j+];zo--;

   }

 return num;

}

int main(){

    for(int i=;i<=;++i)scanf("%d",&a[i]),x=x*+a[i];jie[]=;int mem=x;

    for(int i=;i<=;++i)jie[i]=jie[i-]*i;

    win=zx_hash();

    q.push(node{zx_hash(x),});

    while(!q.empty()){

        int u=q.front().first,nn=q.front().second;q.pop();

        if(u==win){

            printf("%d\n",nn);

            tag=;

            break;

        }

        x=anti_hash(u);

        for(int i=;i>=;--i)d1[r1[i]]=x%,d2[r2[i]]=x%,x/=;

        int x1=,x2=;

        for(int i=;i<=;++i)x1=x1*+d1[i],x2=x2*+d2[i];

        x1=zx_hash(x1);x2=zx_hash(x2);

        if(!ji[x1])ji[x1]=u,q.push(node{x1,nn+});

        if(!ji[x2])ji[x2]=u,q.push(node{x2,nn+});

    }

    if(!tag){

        printf("UNSOLVABLE");

        return ;

    }

    x=mem;x=zx_hash(x);

    while(win!=x){

        ans[++tot]=win;win=ji[win];

    }

    ans[++tot]=x;

    for(int i=tot;i>=;--i){

        int qq=anti_hash(ans[i]);

        for(int j=;j>=;--j)a[j]=qq%,qq/=;

        printf("%d %d %d\n%d %d %d\n%d %d %d\n\n",a[],a[],a[],a[],a[],a[],a[],a[],a[]);

    }

    return ;

}

巴特西

[ZJOI2005]九数码游戏(BFS+hash)

最新文章

热门文章