[HDU 1430]マジックボード

マジックプレート
Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 1988    Accepted Submission(s): 407
Problem Description
ルービック氏は、ルービックが世界を風靡してから間もなく、その簡略化版である魔板を発明した.マジックボードは8つの同じ大きさのブロックからなり、各ブロックの色は異なり、数字1-8でそれぞれ表すことができます.いずれのタイミングでもマジックボードの状態は、キューブの色のシーケンスで表すことができます.マジックボードの左上隅から、各ブロックの色番号を時計回りに順番に書き、得られた数字のシーケンスは、このときのマジックボードの状態を表すことができます.例えば、シーケンス(1,2,3,4,5,6,7,8)は、マジックボードの状態が次のように表される.
1 2 3 4
8 7 6 5
魔板には、3つの異なる操作を加えることができ、具体的な操作方法は以下の通りである.
A:上下2行を入れ替えて、上の図のように状態87654321に変換できます.
B:各行を同時に右にシフトし、図のように41236785に変換できます.
C:真ん中の4つのブロックが時計回りに1つ回転し、上記のように17245368に変換できます.
魔板の初期状態とターゲット状態をあげます.初期状態から目状態への変換数が最も少ない変換ステップを与えてください.複数の変換スキームがあれば、辞書順が最も小さいものを取ります.
 
Input
各試験データのセットは、魔板の初期状態と目状態を表す2行を含む.
 
Output
テストデータのセットごとに、問題を満たす変換手順を出力します.
 
Sample Input
12345678
17245368
12345678
82754631
  
Sample Output
C
AC
 
すべての答えを前に処理

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

#include <map>

#include <string>

using namespace std;

#define N 326888



bool vis[N];

string way[N];

int fac[]={1,1,2,6,24,120,720,5040,40320,326880};



struct node

{

    string s;

    string op;

};



int Find(string &s)   

{

    int i,j,res=0;

    bool has[10]={0};

    for(i=0;i<9;i++)

    {

        int x=s[i]-'0',y=0;

        for(j=1;j<x;j++)

        {

            if(!has[j]) y++;

        }

        res+=y*fac[8-i];

        has[x]=1;

    }

    return res+1;

}



void bfs()

{

    int i,j;

    node now,next;

    queue<node> q;

    memset(vis,0,sizeof(vis));

    now.s="12345678";

    now.op="";

    q.push(now);

    vis[Find(now.s)]=1;

    while(!q.empty())

    {

        now=q.front();

        q.pop();

        way[Find(now.s)]=now.op;

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

        {

            next=now;

            if(i==1)

            {

                next.op+='A';

                swap(next.s[0],next.s[7]);

                swap(next.s[1],next.s[6]);

                swap(next.s[2],next.s[5]);

                swap(next.s[3],next.s[4]);

            }

            else if(i==2)

            {

                next.op+='B';

                char ch=next.s[3];

                for(j=3;j>=1;j--) next.s[j]=next.s[j-1];

                next.s[0]=ch;

                ch=next.s[4];

                for(j=4;j<7;j++) next.s[j]=next.s[j+1];

                next.s[7]=ch;

            }

            else

            {

                next.op+='C';

                char ch=next.s[1];

                next.s[1]=next.s[6];

                next.s[6]=next.s[5];

                next.s[5]=next.s[2];

                next.s[2]=ch;

            }

            if(!vis[Find(next.s)])

            {

                vis[Find(next.s)]=1;

                q.push(next);

            }

        }

    }

}

int main()

{

    bfs();

    string s1,s2;

    while(cin>>s1>>s2)

    {

        map<char,char> mp;

        for(int i=0;i<8;i++) //  、     ，WA- -

        {

            mp[s1[i]]=i+1+'0';

        }

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

        {

            s2[i]=mp[s2[i]];

        }

        cout<<way[Find(s2)]<<endl;

    }

    return 0;

}