或许是我的处理问题...这题代码给敲了这么多...就是一个裸的BFS+Hash判重...判重就是把矩阵看成一个9位的四进制数...
开始我还想写A*...自以为是的用每个点的值到12的差之和来构造g(x)....结果就是搜不对..后来仔细一想...这题的g函数反正我是一下想不出....直接用BFS给水了..速度不太给力的说...应该能用A*的感觉~~
Program:
/* ID: zzyzzy12 LANG: C++ TASK: clocks */ #include<iostream> #include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> #include<queue> using namespace std; struct node { int s[3][3],way[50],num; }h,k; queue<node> myqueue; int change(int x) { if (x==12) return 3; if (x==3) return 6; if (x==6) return 9; return 12; } int had(node h) { int i,j,ans=0,k=1; for (i=0;i<3;i++) for (j=0;j<3;j++) { ans+=(k*h.s[i][j]/3); k*=4; } return ans; } bool f[3000000]; void pushit(node h,int p) { node k=h; int temp; k.num=h.num+1; k.way[k.num]=p; if (p==1) { k.s[0][0]=change(k.s[0][0]); k.s[0][1]=change(k.s[0][1]); k.s[1][0]=change(k.s[1][0]); k.s[1][1]=change(k.s[1][1]); }else if (p==2) { k.s[0][0]=change(k.s[0][0]); k.s[0][1]=change(k.s[0][1]); k.s[0][2]=change(k.s[0][2]); }else if (p==3) { k.s[0][1]=change(k.s[0][1]); k.s[0][2]=change(k.s[0][2]); k.s[1][1]=change(k.s[1][1]); k.s[1][2]=change(k.s[1][2]); }else if (p==4) { k.s[0][0]=change(k.s[0][0]); k.s[1][0]=change(k.s[1][0]); k.s[2][0]=change(k.s[2][0]); }else if (p==5) { k.s[0][1]=change(k.s[0][1]); k.s[1][0]=change(k.s[1][0]); k.s[1][1]=change(k.s[1][1]); k.s[1][2]=change(k.s[1][2]); k.s[2][1]=change(k.s[2][1]); }else if (p==6) { k.s[0][2]=change(k.s[0][2]); k.s[1][2]=change(k.s[1][2]); k.s[2][2]=change(k.s[2][2]); }else if (p==7) { k.s[1][0]=change(k.s[1][0]); k.s[1][1]=change(k.s[1][1]); k.s[2][0]=change(k.s[2][0]); k.s[2][1]=change(k.s[2][1]); }else if (p==8) { k.s[2][0]=change(k.s[2][0]); k.s[2][1]=change(k.s[2][1]); k.s[2][2]=change(k.s[2][2]); }else if (p==9) { k.s[1][1]=change(k.s[1][1]); k.s[1][2]=change(k.s[1][2]); k.s[2][1]=change(k.s[2][1]); k.s[2][2]=change(k.s[2][2]); } temp=had(k); if (!f[temp]) { f[temp]=true; myqueue.push(k); } } bool ok(node h) { int i,j; for (i=0;i<3;i++) for (j=0;j<3;j++) if (h.s[i][j]!=12) return false; return true; } int main() { freopen("clocks.in","r",stdin); freopen("clocks.out","w",stdout); for (int i=0;i<3;i++) for (int j=0;j<3;j++) scanf("%d",&h.s[i][j]); h.num=0; while (!myqueue.empty()) myqueue.pop(); myqueue.push(h); memset(f,false,sizeof(f)); while (!myqueue.empty()) { h=myqueue.front(); myqueue.pop(); if (ok(h)) break; for (int i=1;i<=9;i++) pushit(h,i); } printf("%d",h.way[1]); for (int i=2;i<=h.num;i++) printf(" %d",h.way[i]); printf("\n"); return 0; }