记录编号	108736	评测结果	AAAAAAAAAA
题目名称	[NOI 2001]聪明的打字员	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	7.749 s
提交时间	2014-07-05 23:06:52	内存使用	6.04 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
class STATE{
public:
	int a[6],cur;
	int tim;
	void print(void){
		cout<<cur<<" ";
		for(int i=0;i<6;i++) cout<<a[i]<<" ";cout<<endl;
	}
};
STATE turnstate(string s){
	STATE ans;
	for(int i=0;i<6;i++) ans.a[i]=s[i]-'0';
	return ans;
}
//分别对应:swap0,swap1,up,down,left,right
STATE operate(STATE s,int cmd){
	if(cmd==0){swap(s.a[s.cur],s.a[0]);}
	else if(cmd==1){swap(s.a[s.cur],s.a[5]);}
	else if(cmd==2){if(s.a[s.cur]<9) s.a[s.cur]++;}
	else if(cmd==3){if(s.a[s.cur]>0) s.a[s.cur]--;}
	else if(cmd==4){if(s.cur>0) s.cur--;}
	else if(cmd==5){if(s.cur<5) s.cur++;}
	return s;
}
bool operator == (STATE s,STATE t){
	for(int i=0;i<6;i++) if(s.a[i]!=t.a[i]) return false;
	return true;
}
STATE start,goal;
bool vis[6][10][10][10][10][10][10]={0};
bool checkvis(STATE s){//如果之前未被访问过则把相应vis标记
	bool &v=vis[s.cur][s.a[0]][s.a[1]][s.a[2]][s.a[3]][s.a[4]][s.a[5]];
	if(!v) return v=true;
	return false;
}
queue<STATE> Q;
void BFS(void){
	if(start==goal){
		printf("0\n");
		return;
	}
	start.tim=0;
	start.cur=0;
	checkvis(start);
	Q.push(start);
	STATE s,t;
	while(true){
		s=Q.front();Q.pop();
		for(int i=0;i<6;i++){
			t=operate(s,i);
			if(checkvis(t)){
				t.tim=s.tim+1;
				Q.push(t);
				if(t==goal){
					printf("%d\n",t.tim);
					return;
				}
			}
		}
	}
}
void read(void){
	string str;
	cin>>str;
	start=turnstate(str);
	cin>>str;
	goal=turnstate(str);
}
int main(){
	freopen("clever.in","r",stdin);
	freopen("clever.out","w",stdout);
	read();
	BFS();
	return 0;
}