poj 3349 数组的hash（最常用、最普通的哈希表建立）

Description

Input

Output

Sample Input

2
1 2 3 4 5 6
4 3 2 1 6 5

Sample Output

Twin snowflakes found.

/**
poj 3349  数字hash
题目大意：每个雪花都有六个分支，用六个整数代表，这六个整数是从任意一个分支开始，朝顺时针或逆时针方向遍历得到的。输入多个雪花，判断是否有形状一致的雪花存在。
解题思路：数字哈希，要注意的是每种雪花可以由多种数字组合表示。
比如输入的是1 2 3 4 5 6，
则2 3 4 5 6 1，3 4  5 6 1 2，……，6 5 4 3 2 1，5 4 3 2 1 6等都是相同形状的。
因此可以在读入一个雪花的时候把这些情况全部放入哈希表中，如果某次插入的时候发生冲突，则说明存在重复的雪花，并且后面的不需要再处理。
*/
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;
const int maxn=1200010;
const int mod=1200007;

int head[maxn],ip;

void init()
{
    memset(head,-1,sizeof(head));
    ip=0;
}
struct note
{
    int num[6];
    int next;
} edge[1200010];

int get_hash(int *num)
{
    int h=0;
    for(int i=0; i<6; i++)
        h+=num[i];///哈希函数，也可以用其他的构造方式
    return h%mod;
}

void insert_hash(int *num,int h)
{
    for(int i=0; i<6; i++)
        edge[ip].num[i]=num[i];
    edge[ip].next=head[h];
    head[h]=ip;
    ip++;

}

bool compare(int *a,int *b)
{
    for(int i=0; i<6; i++)
    {
        if(a[i]!=b[i])
            return false;
    }
    return true;
}

bool search_hash(int *num)
{
    int h=get_hash(num);
    for(int i=head[h]; i!=-1; i=edge[i].next)
    {
        if(compare(num,edge[i].num))
            return true;
    }
    insert_hash(num,h);
    return false;
}

int main()
{
    int n,num[2][15];
    scanf("%d",&n);
    init();
    int flag=0;
    while(n--)
    {
        for(int i=0; i<6; i++)
        {
            scanf("%d",&num[0][i]);
            num[0][i+6]=num[0][i];
        }
        if(flag) continue;
        for(int i=0; i<6; i++)
        {
            num[1][i+6]=num[1][i]=num[0][5-i];
        }
        for(int i=0; i<6; i++)
        {
            if(search_hash(num[0]+i)||search_hash(num[1]+i))
            {
                flag=1;
                break;
            }
        }
    }
    if(flag)printf("Twin snowflakes found.\n");
    else printf("No two snowflakes are alike.\n");
    return 0;
}