记录编号	74520	评测结果	AAAAAAAA
题目名称	魔板	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.054 s
提交时间	2013-10-25 19:46:15	内存使用	0.27 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<deque>
using namespace std;
//第i位表示十进制右起第i位
//8765
//4321
//这个数表示为十进制数87654321
int pow10[]={1,1e1,1e2,1e3,1e4,1e5,1e6,1e7,1e8};
int getds(int x,int a,int b){//x的a~b位
	int temp=x/(pow10[a-1]);
	return temp%pow10[b-a+1];
}
int opa(int x){//对x表示的状态进行A操作
	//交换上下两行
	//前四位和后四位顺序颠倒
	int a=getds(x,1,4);
	int b=getds(x,5,8);
	return a*pow10[4]+b;
}
int opb(int x){//对x表示的状态进行B操作
	//原来是87654321
	//现在是58761432
	int a1=getds(x,1,1);
	int b1=getds(x,2,4);
	int a2=getds(x,5,5);
	int b2=getds(x,6,8);
	return a1*pow10[3]+b1+a2*pow10[7]+b2*pow10[4];
}
int opc(int x){//对x表示的状态进行C操作
	//原来是87654321
	//现在是83754261
	int a[9]={0};
	a[1]=getds(x,1,1),a[2]=getds(x,6,6),a[3]=getds(x,2,2),a[4]=getds(x,4,4);
	a[5]=getds(x,5,5),a[6]=getds(x,7,7),a[7]=getds(x,3,3),a[8]=getds(x,8,8);
	int ans=0;
	for(int i=1;i<=8;i++) ans+=a[i]*pow10[i-1];
	return ans;
}
class LAST{
public:
	int pos;//在队中的位置
	char opt;//操作
};
set<int> hash;
vector<pair<int,LAST> > Q;
deque<char> ans;
int goal;
int original=12348765;
void answer(void){
	int x=Q.size()-1;
	while(x!=0){
		ans.push_front(Q[x].second.opt);
		x=Q[x].second.pos;
	}
	printf("%d\n",ans.size());
	int i;
	for(i=0;i<ans.size();i++) printf("%c",ans[i]);
}
bool exist(int x){
	return hash.find(x)!=hash.end();
}
void BFS(void){
	int tot;
	int now;
	LAST lp;
	int temp;
	for(tot=0;tot<Q.size();tot++){
		now=Q[tot].first;
		lp=Q[tot].second;
		temp=opa(now);
		//cout<<now<<endl;
		if(!exist(temp)) Q.push_back(make_pair(temp,(LAST){tot,'A'})),hash.insert(temp);
		if(temp==goal){
			answer();
			return;
		}
		temp=opb(now);
		if(!exist(temp)) Q.push_back(make_pair(temp,(LAST){tot,'B'})),hash.insert(temp);
		if(temp==goal){
			answer();
			return;
		}
		temp=opc(now);
		if(!exist(temp)) Q.push_back(make_pair(temp,(LAST){tot,'C'})),hash.insert(temp);
		if(temp==goal){
			answer();
			return;
		}
	}
}
void read(void){
	//8765
	//4321
	int a[9]={0};
	int i;
	scanf("%d%d%d%d%d%d%d%d",&a[8],&a[7],&a[6],&a[5],&a[1],&a[2],&a[3],&a[4]);
	goal=0;
	for(i=1;i<=8;i++) goal+=a[i]*pow10[i-1];
}
void work(void){
	if(goal==original){
		printf("0\n");
		return;
	}
	Q.push_back(make_pair(original,(LAST){-1,-1}));
	hash.insert(original);
	BFS();
}
int main(){
	freopen("msquare.in","r",stdin);
	freopen("msquare.out","w",stdout);
	read();
	work();
	return 0;
}