BFS搜索题。代码写的比较乱，用一个set来存储已经访问过的结点。analysis中的标程有不少可以学习的地方，如几个操作的变换，用转换数组来写，代码清晰明了，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;
}