USACO Section 1.4 clocks - 好恶心的搜索题

或许是我的处理问题...这题代码给敲了这么多...就是一个裸的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;   
}