记录编号	169774	评测结果	AAAAAAAA
题目名称	时钟	最终得分	100
用户昵称	NVIDIA	是否通过	通过
代码语言	C++	运行时间	1.096 s
提交时间	2015-07-10 15:59:20	内存使用	13.43 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<vector>
#define mem(a) memset(a,0,sizeof(a));
using namespace std;
typedef int State[9];
const int MAX=320000;
const int MAXSIZE=100003;
int head[MAXSIZE],F[MAX],next[MAX],move[MAX];
State st[MAX];
const State goal={3,3,3,3,3,3,3,3,3};
const char mo[9][6]={"abde","abc","bcef","adg","bdefh","cfi","degh","ghi","efhi"};
void shuru()
{
    mem(head);mem(next);
    int i;
    for(i=0;i<9;i++)
	{cin>>st[0][i];st[0][i]=st[0][i]/3-1;}
}
int hash(State& s)
{
    int i,a=0;
    for(i=0;i<9;i++)a=a*10+s[i];
    return a%MAXSIZE;
}
bool insert(int a)
{
    int h=hash(st[a]);
    int u=head[h];
    while(u)
    {
        if(memcmp(st[u],st[a],sizeof(st[a]))==0)return false;
        u=next[u];
    }
    next[a]=head[h];
    head[h]=a;
    return true;
}
void print(int p)
{
    if(!F[p]){cout<<move[p];return ;}
    print(F[p]);
    cout<<" "<<move[p];
}
void BFS()
{
    int rear=1,front=0;
    for(;;)
    {
        State& s=st[front];
        if(memcmp(s,goal,sizeof(goal))==0){print(front);cout<<endl;return ;}
        int i;
        for(i=0;i<9;i++)
        {
            State& t=st[rear];
            memcpy(&t,&s,sizeof(s));
            int len=strlen(mo[i]),j;
            for(j=0;j<len;j++)
                t[mo[i][j]-'a']=(t[mo[i][j]-'a']+1)%4;
            if(insert(rear)){move[rear]=i+1;F[rear++]=front;}
        }
        front++;
    }
}
int main()
{
    freopen("clocks.in","r",stdin);
	freopen("clocks.out","w",stdout);
	shuru();
    BFS();
    return 0;
}
//4个时间3，6,9,12依次转化为0,1,2,3；所以是9个3