?BFS搜索題。代碼寫的比較亂，用一個set來存儲已經(jīng)訪問過的結(jié)點。analysis中的標程有不少可以學(xué)習(xí)的地方，如幾個操作的變換，用轉(zhuǎn)換數(shù)組來寫，代碼清晰明了，encode方法就省去了set。我通過保存整個樹來輸出解，標程通過反向操作，來輸出解，做法很巧妙。
#include?<iostream>
#include?<fstream>
#include?<set>
#include?<queue>
using?namespace?std;
ifstream?fin("msquare.in");
ofstream?fout("msquare.out");
#ifdef?_DEBUG
#define?out?cout
#define?in?cin
#else
#define?out?fout
#define?in?fin
#endif
int?final[8];
set<int>visited;
char?result[8*7*6*5*4*3*2*1+1];
struct?queue_node{
????int?current[8];
????queue_node?*parent;
????char?op;
};
void?op(int?*current,char?c)
{
????int?tmp;
????switch(c){
????????case?'A':
????????????for(int?i=0;i<4;++i)
????????????????swap(current[i],current[7-i]);
????????????break;
????????case?'B':
????????????tmp?=?current[3];
????????????for(int?i=3;i>=1;--i)
????????????????current[i]?=?current[i-1];
????????????current[0]?=?tmp;
????????????tmp?=?current[4];
????????????for(int?i=4;i<=6;++i)
????????????????current[i]?=?current[i+1];
????????????current[7]?=?tmp;
????????????break;
????????case?'C':
????????????tmp?=?current[6];
????????????current[6]?=?current[5];
????????????current[5]?=?current[2];
????????????current[2]?=?current[1];
????????????current[1]?=?tmp;
????????????break;
????}
}
int?cur_value(int?*cur)
{
????int?res?=?0;
????for(int?i=0;i<8;++i){
????????res*=10;
????????res+=cur[i];
????}
????return?res;
}
void?solve()
{
????for(int?i=0;i<8;++i){
????????in>>final[i];
????}
????queue<queue_node*>?q;
????queue_node?*node?=?new?queue_node;
????for(int?i=0;i<8;++i)
????????node->current[i]?=?i+1;
????node->parent?=?NULL;
????q.push(node);
????while(?!q.empty()?){
????????queue_node?*node?=?q.front();
????????q.pop();
????????int?cur?=?cur_value(node->current);
????????if(?visited.find(?cur)?!=?visited.end())
????????????continue;
????????visited.insert(cur);
????????bool?ok?=?true;
????????for(int?i=0;i<8;++i){
????????????if(node->current[i]!=final[i]){
????????????????ok?=?false;
????????????????break;
????????????}
????????}
????????if(ok){
????????????int?i?=?0;
????????????while(node->parent!=NULL){
????????????????result[i++]?=?node->op;
????????????????node=node->parent;
????????????}
????????????if(i==0){
????????????????out<<0<<endl<<endl;
????????????????exit(0);
????????????}
????????????out<<i<<endl;
????????????int?j;
????????????i--;
????????????for(j=0;i>=0;i--,j++){
????????????????out<<result[i];
????????????????if(j%60==59)?out<<endl;
????????????}
????????????
????????????if(j%60!=0)
????????????????out<<endl;
????????????exit(0);
????????}
????????for(char?c='A';c<='C';++c){
????????????queue_node?*?n?=?new?queue_node;
????????????memcpy(n->current,node->current,sizeof(node->current));
????????????op(n->current,c);
????????????n->op?=?c;
????????????n->parent?=?node;
????????????q.push(n);
????????}
????}
}
int?main(int?argc,char?*argv[])
{
????solve();?
????return?0;
}