POJ 3349 Snowflake Snow Snowflakes

上次在BFS的时候需要hash判重，但是很少接触hash的用法，其实还是和数据结构讲得一样，就是用一个公式起到一个映射的作用，用在搜索上可是缩小查找范围。

代码：

[cpp]
#include<iostream>
#include<vector>
using namespace std;
#define maxn 10949 //hash的大小最好是素数
vector<int> hash[maxn];
int arm[100005][6];
bool comp(int a,int b) //判断雪花是否相同忘了return false 害了我wa了4次。
{
     int i,j,k;
     for( i=0;i<6;i++){
          if( arm[a][0]==arm[b][i]){
              for( j=(i-1+6)%6, k=1 ; k<6 && arm[a][k]==arm[b][j]; j=((--j)+6)%6, k++);//逆时针比较
              if( k==6 ) return true;
              for( j=(i+1)%6 ,k=1; k<6 && arm[a][k]==arm[b][j]; j=(++j)%6 ,k++) ; //顺时针
              if( k==6) return true;
          }
     }
     return false;
}
int main()
{
    int n,i,sum,j,len,r;
    while( scanf("%d",&n)!=EOF){

           memset(arm,0,sizeof(arm));
           for( i=0;i<maxn;i++) hash[i].clear();
           bool flag=false;

           for( i=0;i<n&&!flag;i++){
                  sum=0;
                  for( j=0;j<6;j++){
                       scanf("%d",&arm[i][j]);
                       sum+=arm[i][j];
                  }
                  r=sum%maxn;
                  len=hash[r].size();
                  for( j=0;j<len;j++){ //在和相同的前提下比较有没有相同的雪花
                       if( comp( i, hash[r][j] ) ){
                           flag=true;
                           break;
                       }
                  }
                  if(!flag) hash[r].push_back(i);
           }
           if( flag){
               for( ;i<n;i++){ //边输入边判断可能还有没有输完的
                      for(j=0;j<6;j++)
                      scanf("%*d");
               }
               printf("Twin snowflakes found.\n");
           }
           else
               printf("No two snowflakes are alike.\n");
    }
    return 0;
}

补充：软件开发 , C++ ,