This post is written in Chinese. Please consider using Google Translate

这道题类似于八数码难题，基本思想是宽搜，使用Hash判重。如果使用一般的八维数组空间可以达到8^8=16777216，会超过USACO的16MB空间限制。所以我们应该对状态进行散列存储，观察发现每位的数字不能重复，存在空间冗余。我们可以对于每个状态建立一个映射，采用康托展开算法。(参见Nocow) 定义cantor(s)为s串大大小顺序。可样将哈希容量缩减到8!=40320。

另外发现，对于魔板当前状态可以由一个8位的8进制数来表示，即无符号32位长整型 unsigned long 表示。 对于魔板的变换可以转化为对一个数字的位运算。这样可以大大提高程序效率。

程序有些长，但是效率很高。

USER: CmYkRgB CmYkRgB [cmykrgb1]
TASK: msquare
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.011 secs, 3476 KB]
   Test 2: TEST OK [0.054 secs, 3444 KB]
   Test 3: TEST OK [0.011 secs, 3476 KB]
   Test 4: TEST OK [0.011 secs, 3472 KB]
   Test 5: TEST OK [0.011 secs, 3480 KB]
   Test 6: TEST OK [0.022 secs, 3476 KB]
   Test 7: TEST OK [0.022 secs, 3476 KB]
   Test 8: TEST OK [0.023 secs, 3484 KB]

All tests OK.

/*
ID: cmykrgb1
PROG: msquare
LANG: C++
*/
#include <iostream>
#include <fstream>
#define MAX 40320
using namespace std;

class state
{
public:
    state()
    {
        comefrom=0;cur=0;cont=0;
    }
    state *comefrom;
    unsigned long cur;
    short cont;
};
state O;
state S[MAX];

class queue
{
private:
    long first,last;
    long list[MAX];
public:
    long size;

    queue()
    {
        reset();
    }

    void reset()
    {
        first=0;
        size=0;
        last=-1;
    }

    void ins(state *comefrom,unsigned long cur,long cont)
    {
        size++;
        last++;
        list[last]=last;
        S[last].comefrom=comefrom;
        S[last].cur=cur;
        S[last].cont=cont;
    }

    long del()
    {
        size--;
        return list[first++];
    }
};

ifstream fi("msquare.in");
ofstream fo("msquare.out");
bool hash[MAX];
char B[4]={0,'A','B','C'};

long fac[8]={1,1,2,6,24,120,720,5040};
unsigned long Finish;

unsigned long cantor(unsigned long S)
{
    long x=0,i,p,k,j;
    bool hash[8]={false};
    for (i=8;i>=2;i--)
    {
        k=S>> 3*(i-1);
        S-=k<<3*(i-1);
        hash[k]=true;
        p=k;
        for (j=0;j<=k-1;j++)
            if (hash[j])
                p--;
        x+=fac[i-1]*p;
    }
    return x;
}

void init()
{
    long i,t;
    for (i=0;i<8;i++)
    {
        fi>>t;
        t--;
        O.cur*=8;
        O.cur+=t;
    }
    Finish=cantor(O.cur);
    hash[0]=true;
}

unsigned long turn(unsigned long S,int f)
{
    long i;
    unsigned long P=0;
    switch (f)
    {
    case 1:
        for (i=1;i<=8;i++)
            P+=(S & (7<< ( (i-1)*3) ) )>> (i-1)*3 << ((8-i)*3);
        return P;
        break;
    case 2:
        P+=(S & 07000)>>3*3;
        P+=(S & 00777)<<3;
        P+=(S & 070000)<<3*3;
        P+=(S & 077700000)>>3;
        return P;
        break;
    case 3:
        P= (S & 070077007);
        P+=(S & 070)<<5*3;
        P+=(S & 0700)>>1*3;
        P+=(S & 0700000)>>3*3;
        P+=(S & 07000000)>>1*3;
        return P;
        break;
    }
}

void print(long ed,long f)
{
    string O;
    state *P=&S[ed];
    char OUT[MAX];
    long cnt=0,i;
    while (P->cont)
    {
        cnt++;
        OUT[cnt]=B[P->cont];
        P=P->comefrom;
    }

    fo << cnt+1<<endl;
    for (i=cnt;i>=1;i--)
        fo << OUT[i];
    fo << B[f] << endl;

    fi.close();
    fo.close();
    exit(0);
}

void bfs()
{
    long i=0,j;
    queue Q;
    Q.ins(&O,001234567,0);
    while (Q.size)
    {
        unsigned long p,ct;
        i=Q.del();
        for (j=1;j<=3;j++)
        {
            p=turn(S[i].cur,j);
            ct=cantor(p);
            if (!hash[ct])
            {
                hash[ct]=true;
                if (ct==Finish)
                    print(i,j);
                Q.ins(&S[i],p,j);
            }
        }
    }
}

int main()
{
    init();
    bfs();
    fo << '0' <<'n'<<'n';
    fi.close();
    fo.close();
    return 0;
}