Vijos1029[晴天小猪历险记之Number] 搜索＋康托展开

康托展开：

康托展开表示的是当前n个元素排列在n个不同元素的全排列中的名次。

比如213在这3个数所有排列中排第3。

那么，对于n个数的排列，康托展开为：

ans=an*(n-1)!+an-1*(n-2)!+…+ai*(i-1)!+…+a2*1!+a1*0!

其中：a从右向左排号 2是a3， 1是a2， 3是a1

a表示每一个数的右边比它小的数的个数

2: 13 1<2 a3=1

1: 3 a2=0

3: a1=0

#include <map>
#include <set>
#include <queue>
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
struct Matrix{
    int m[][], step;
}sta;

int dx[]={,}, dy[]={,};
int f[]={,,,,,,,,};
int vis[];
set<int> ans;

int Contor( Matrix s ){
    int ans=;
    for ( int i=; i<=; i++ ){
        int tmp=;
        for ( int j=i+; j<=; j++ )
            if( s.m[((i-)/)+][((i-)%)+] > s.m[((j-)/)+][((j-)%)+] ) tmp++;
        ans+=tmp*f[i]; 
    }
    return ans;
}



void bfs(){
    queue<Matrix> Q;
    memset(vis,,sizeof(vis));
    vis[Contor(sta)]=;
    sta.step=;
    Q.push(sta);
    while( !Q.empty() ){
        Matrix u=Q.front();
        Q.pop();
        if( ans.count(Contor(u)) ){
            printf("%d\n", u.step );
            return ;
        }
        for ( int i=; i<=; i++ ){
            for ( int j=; j<=; j++ ){
                for ( int k=; k<=; k++ ){
                    int i0=i+dx[k];
                    int j0=j+dy[k];
                    if( i0<= && j0<= ){
                        Matrix u1=u;
                        swap( u1.m[i][j], u1.m[i0][j0] );
                        int ct=Contor(u1);
                        u1.step++;
                        if( vis[ct] ) continue;
                        vis[ct]=;
                        Q.push(u1);
                    }
                }
            }
        }
    }
    puts("-1");
}
int main(){
    ans.clear();
    ans.insert(); ans.insert(); ans.insert(); ans.insert();
    ans.insert(); ans.insert(); ans.insert(); ans.insert();
    while( scanf("%d%d%d", &sta.m[][], &sta.m[][], &sta.m[][])== ){
        for ( int i=; i<=; i++ )
            for ( int j=; j<=; j++ )
                scanf("%d", &sta.m[i][j] );
        bfs();
    }
    return ;
}