题目大意

用3种方法将魔板还原成初始的状态
计算最小的次数

思路

因为是最少次数，所以很容易想到bfs，但是判重会很慢，所以就要用hash来优化它，并且每一次的交换都是有规律的

#include 
#include 
#include 
#define M 1000007
using namespace std;
string state[M+1];
int h[M+1],f[M+1],w[M+1],ans=0;
int rule[4][9]={{},{0,8,7,6,5,4,3,2,1},{0,4,1,2,3,6,7,8,5},{0,1,7,2,4,5,3,6,8}};
int find(string x)
{
    int s;
    s=atoi(x.c_str());
    int i=s%M;
    while (h[i]!=s&&h[i]!=0) i=(i+1)%M;
    bool fl=0;
    if (h[i]==s) fl=true;
    else fl=false;
    h[i]=s;
    return fl;
}
int print(int x)
{
    if (f[x]!=0)
    {
        ans++;
        print(f[x]);
    }
    if (f[x]==0) printf("%d\n",ans); else
    if (w[x]==1) printf("A"); else
    if (w[x]==2) printf("B"); else
    if (w[x]==3) printf("C"); 
    return 0;
}
int bfs()
{
    int head=0,tail=1;
    if (state[1]==state[0])
    {
        print(1);
        return 0;
    }
    while (head<=tail)
    {
        head++;
        for (int i=1;i<=3;i++)
        {
            tail++;
            f[tail]=head;
            w[tail]=i;
            for (int j=1;j<=8;j++)
                state[tail]=state[tail]+state[head][rule[i][j]-1];
            if (find(state[tail])==true)
            {   
                state[tail]="";
                tail--;
            }
            if (state[tail]==state[0])
            {
                print(tail);
                return 0;
            }
        }
    }
}
int main()
{
    string s;
    for (int i=1;i<=8;i++)
    {
        char x=getchar();
        while (x==' ')x=getchar();
        s=s+x;
    }
    state[0]=s;
    state[1]="12345678";

    h[12345678%M]=12345678;
    bfs();
    return 0;
}