Beyond the Void

/*
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;
}