HDU 3567 Eight II BFS预处理

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题意：就是八数码问题，给你开始的串和结束的串，问你从开始到结束的最短且最小的变换序列是什么

分析：我们可以预处理打表，这里的这个题可以和HDU1430魔板那个题采取一样的做法

预处理打表，因为八数码问题实际上是每个小块位置的变化，上面的数字只是用来标记位置的，

所以通过映射将初末序列进行置换就好了，然后因为每次的x字符的置换位置不一样

所以需要以123456789这个初始串打9遍表就好了733ms

#include <iostream>

#include <cstdio>

#include <vector>

#include <cstring>

#include <algorithm>

#include <string>

#include <cmath>

#include <queue>

using namespace std;

const int N=;

int fac[]= {,,,,,,,,,};

int aim;

int cantor(char s[])

{

    int ans=;

    for(int i=,j=; i<=; ++i,--j)

    {

        int tmp=;

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

            if(s[i]>s[k])++tmp;

        ans+=(tmp*fac[j]);

    }

    return ans;

}

struct Node

{

    char s[];

    int hs;

};

struct asd

{

   bool vis;

   char c;

   int pre;

}o[][];

queue<Node>q;

void bfs(int pos)

{

    Node a;

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

        a.s[i]=''+i;

    aim=a.hs=cantor(a.s);

    o[pos][a.hs].vis=;

    q.push(a);

    while(!q.empty())

    {

        a=q.front();

        q.pop();

        int now=a.hs;

        int x;

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

            if(a.s[i]==''+pos)x=i;

        if(x+<)

        {

            bool flag=;

            swap(a.s[x],a.s[x+]);

            a.hs=cantor(a.s);

            if(o[pos][a.hs].vis)

                flag=;

            if(!flag)

            {

                o[pos][a.hs].vis=;

                o[pos][a.hs].c='d';

                o[pos][a.hs].pre=now;

                q.push(a);

            }

            swap(a.s[x],a.s[x+]);

        }

        if(x%!=)

        {

            bool flag=;

            swap(a.s[x],a.s[x-]);

            a.hs=cantor(a.s);

            if(o[pos][a.hs].vis)

                flag=;

            if(!flag)

            {

                o[pos][a.hs].vis=;

                o[pos][a.hs].c='l';

                o[pos][a.hs].pre=now;

                q.push(a);

            }

            swap(a.s[x],a.s[x-]);

        }

        if(x%)

        {

            bool flag=;

            swap(a.s[x],a.s[x+]);

            a.hs=cantor(a.s);

           if(o[pos][a.hs].vis)

                flag=;

            if(!flag)

            {

                o[pos][a.hs].vis=;

                o[pos][a.hs].c='r';

                o[pos][a.hs].pre=now;

                q.push(a);

            }

            swap(a.s[x],a.s[x+]);

        }

        if(x->)

        {

            bool flag=;

            swap(a.s[x],a.s[x-]);

            a.hs=cantor(a.s);

           if(o[pos][a.hs].vis)

                flag=;

            if(!flag)

            {

                o[pos][a.hs].vis=;

                o[pos][a.hs].c='u';

                o[pos][a.hs].pre=now;

                q.push(a);

            }

            swap(a.s[x],a.s[x-]);

        }

    }

}

char s[],t[];

string res;

void getres(int u,int pos)

{

    while(u!=aim)

    {

       res=res+o[pos][u].c;

       u=o[pos][u].pre;

    }

}

char mat[];

int main()

{

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

     for(int j=;j<=;++j)

      o[j][i].vis=;

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

       bfs(i);

    int T,cas=;

    scanf("%d",&T);

    while(T--)

    {

         scanf("%s%s",s+,t+);

         int flag;

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

         {

             if(s[i]=='X')s[i]='',flag=i;

             if(t[i]=='X')t[i]='';

             mat[s[i]-'']=i+'';

         }

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

            t[i]=mat[t[i]-''];

        int ans=cantor(t);

        res.clear();

        getres(ans,flag);

        printf("Case %d: %d\n",++cas,res.size());

        reverse(res.begin(),res.end());

        cout<<res<<endl;

    }

    return ;

}