HDU1430;魔板（BFS+康托展开）

传送门

题意

给出初始序列与终止序列，给出三种操作，问最少经过几次操作能使初始->终止，输出操作（字典序最小）

分析

字符串只有8个字符，使用康托展开。

1.BFS将所有序列从"12345678"操作得到，能够保证字典序与次数最小（采用string）

2.接下来将初始序列变成"12345678",相应终止序列也变化，该操作由下列代码实现

R(i,0,8) pos[s1[i]-'0']=i+1;

R(i,0,8) s2[i]=pos[s2[i]-'0'];

代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define F(i,a,b) for(int i=a;i<=b;++i)

#define R(i,a,b) for(int i=a;i<b;++i)

#define mem(a,b) memset(a,b,sizeof(a))

#define cpy(a,b) memcpy(a,b,sizeof(b))

string s1,s2,ans[100100];

int a[10]={1,1,2,6,24,120,720,5040},pos[10];

bool vis[100100];

int cal(string &s)//cnt=a[i]*(n-i-1)!

{

    int ret=0;

    R(i,0,7)

    {

        int tmp=0;

        R(j,i+1,8) if(s[i]>s[j]) tmp++;

        ret+=tmp*a[7-i];

    }

    //printf("ret=%d\n",ret);

    return ret;

}

struct node

{

    string s;

    int value;

};

void op1(string &s)

{

    F(i,1,4) swap(s[i-1],s[8-i]);

}

void op2(string &s)

{

    for(int i=3;i;--i) swap(s[i],s[i-1]);

    for(int i=4;i<7;++i) swap(s[i],s[i+1]);

}

void op3(string &s)

{

    swap(s[1],s[6]);swap(s[6],s[5]);swap(s[2],s[5]);

}

queue<node>q;

void bfs()

{

    string s="12345678";

    node p;

    p.s=s;

    p.value=cal(s);

    vis[p.value]=1;

    ans[p.value]="";

    q.push(p);

    while(!q.empty())

    {

        //puts("1");

        p=q.front();q.pop();

        //if(vis[p.value]) continue;

        F(i,1,3)

        {

            if(i==1)

            {

                node pp=p;

                op1(pp.s);

                pp.value=cal(pp.s);

                if(!vis[pp.value])

                {

                    vis[pp.value]=1;ans[pp.value]=ans[p.value]+'A';

                    q.push(pp);

                }

            }

            if(i==2)

            {

                node pp=p;

                op2(pp.s);

                pp.value=cal(pp.s);

                if(!vis[pp.value])

                {

                    vis[pp.value]=1;ans[pp.value]=ans[p.value]+'B';

                    q.push(pp);

                }

            }

            if(i==3)

            {

                node pp=p;

                op3(pp.s);

                pp.value=cal(pp.s);

                if(!vis[pp.value])

                {

                    vis[pp.value]=1;ans[pp.value]=ans[p.value]+'C';

                    q.push(pp);

                }

            }

        }

    }

}

int main()

{

    bfs();

    while(cin>>s1>>s2)

    {

        R(i,0,8) pos[s1[i]-'0']=i+1;

        R(i,0,8) s2[i]=pos[s2[i]-'0'];

        cout<<ans[cal(s2)]<<endl;

    }

    return 0;

}

巴特西

HDU1430;魔板（BFS+康托展开）

传送门

题意

分析

代码

最新文章

热门文章