2013多校第四场 C题

解题思路:

　　首先考虑题目数据大小范围, 总共9个不同数字的全排列, 9! = 3*10^5

　　假设N = 9!, 意味着,拼图的状态有N种, 将其看成顶点.[1,N]

　　则因为每次只能够移动0, 且每次只能向四个方向移动,则意味着每个顶点至多有四条边.且每条边的

长度为1.

　　假定序列 (876543210) 目标序列, 其编号为 st, 则我们可以通过求 

　　单源点的最短路. 求出从st出发到其他顶点v的最短距离 dis[v].

　　那么对于T次询问操作. 我们只需要O(1)的时间 输出dis[v]就可以了.　

　　另外还有个问题就是. 对于 (0,1,..,8)的全排列,如何唯一编号.这里就用到了 康托展开.

　　我们其实只要知道结论就可以了.:

　　　　对于一个(1,2,3,..,n)的全排列中的某个排列:  An,An-1,..,A1, 其前面有多少个比它小.(换句话说就是第几个排列)

　　　　假定排列序号为 K,  K = an*(n-1)! + an-1*(n-2)! + ... + a1*0!    ,

　　　　其中 ai 表示 第i位后面有多少个数比 Ai小.

　　每次处理排列唯一编号需要时间为 10*10 = 100

　　使用BFS层次搜索,从st开始搜索所有节点,时间复杂度为 O(N), 

　　总时间复杂度为  O(N*100) =  10^7

　　另外, 此题是 八数码问题.  有多种解法.

　　　　1. 因为N不大,可以直接打表然后输出

　　　　2. 使用启发式搜索 A*, IDA*

　　　　3. 其它算法.

#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <cstdio>
#include <cstring>

using namespace std;

#define MAXN 400000
struct node
{
    int s[9];
    int t;
};
int mp[MAXN];
int fac[9]= {1,1,2,6,24,120,720,5040,40320};

int change_to_int(int s[])
{
    int t=0;
    int count;
    for(int i=0; i<9; i++)
    {
        count=0;
        for(int j=i+1; j<9; j++)
        {
            if(s[i]>s[j])
                count++;
        }
        t+=count*fac[9-i-1];
    }
    return t+1;
}

node change(node a,int i)
{
    int x;
    for(int j=0; j<9; j++)
    {
        if(a.s[j]==0)
        {
            x=j;
        }
//        if(a.s[j]>=9||a.s[j]<0)
//            printf("error!\n");//useless
    }
    if(i==0)
    {
        if(x<3)
            return a;
        else
        {
            swap(a.s[x],a.s[x-3]);
            return a;
        }
    }
    if(i==1)
    {
        if(x>=6)
            return a;
        else
        {
            swap(a.s[x],a.s[x+3]);
            return a;
        }
    }
    if(i==2)
    {
        if(x==6||x==3||x==0)
        {
            return a;
        }
        else
        {
            swap(a.s[x],a.s[x-1]);
            return a;
        }

    }
    if(i==3)
    {
        if(x==8||x==5||x==2)
            return a;
        else
        {
            swap(a.s[x],a.s[x+1]);
            return a;
        }
    }
}

void BFS()
{
    node a,b;
    int x;
    queue<node> v;
    for(int i=8; i>=0; i--)
        a.s[8-i]=i;
    a.t=1;
    mp[change_to_int(a.s)]=1;
    v.push(a);
    while(!v.empty())
    {
        a=v.front();
        v.pop();
        for(int i=0; i<4; i++)
        {
            b=change(a,i);
            b.t++;
            x=change_to_int(b.s);
            if(mp[x]==0)
            {
                mp[x]=b.t;
                v.push(b);
            }
        }
    }
}

int main()
{
    int n;
    node sd;
    memset(mp,0,sizeof(mp));
    BFS();
    scanf("%d",&n);
    while(n--)
    {
        for(int i=0; i<9; i++)
            scanf("%d",&sd.s[i]);
        int x=change_to_int(sd.s);
        if(mp[x]==0)
            printf("impossible!\n");
        else
            printf("%d\n",mp[x]-1);
    }
}