Description

Input

Output

Sample Input

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

Sample Output

Twin snowflakes found.

Source

解题思路：

雪花有六个角。每一个角有一个长度。按顺时针或者逆时针给出，起点是随机的。两个雪花同样当且仅当每一个角的长度一样，且必须是连续的，比方   2 3 1  4 5 6 和 2 1 3  4 5 6就不行，1 2 3 4 5 6    4 3 2 1 6 5是一样的（第二个逆时针给出）。给出一堆雪花的六个角的长度。问这里面能不能找到两个同样的雪花。

1. 两个雪花同样的前提条件是，它们雪花六个角的长度和相等。

把每一个雪花依照长度映射到哈希表中。

这里哈希表用 vector< snowflake> hs[]. 当 hs[i].size()>1时，说明hs[i][j] 和hs[i][k]有可能是两个同样的雪花，仅仅要在hs[i]里面查找就能够了。

2. 怎么推断两个雪花a,b同样？分两步，一， 固定a，用b的每一个边和a的第一条边对齐，然后顺时针比較a,b的每一条边。二，固定a,用b的每一个边和a的第一条边对齐，然后逆时针比較a,b的每一条边。

Ps：以此题哀悼下考砸的数据结构。。

。。考试的时候我居然连拉链法解决冲突都不知道。。

代码：

#include <iostream>
#include <stdio.h>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn=100002;
const int prime=99991;

struct SnowFlake
{
    int len[6];
}snow[maxn];

vector<SnowFlake>hs[prime];

void Hash(SnowFlake s)//映射
{
    int addr=(s.len[0]+s.len[1]+s.len[2]+s.len[3]+s.len[4]+s.len[5])%prime;
    hs[addr].push_back(s);
}

bool cmp(SnowFlake a,SnowFlake b)//比較两个雪花是否同样
{
    for(int i=0;i<6;i++)
    {
        if(a.len[0]==b.len[i]&&a.len[1]==b.len[(i+1)%6]&&a.len[2]==b.len[(i+2)%6]&&
           a.len[3]==b.len[(i+3)%6]&&a.len[4]==b.len[(i+4)%6]&&a.len[5]==b.len[(i+5)%6])
           return true;//固定a。顺时针比較
        if(a.len[0]==b.len[i]&&a.len[1]==b.len[(i+5)%6]&&a.len[2]==b.len[(i+4)%6]&&
           a.len[3]==b.len[(i+3)%6]&&a.len[4]==b.len[(i+2)%6]&&a.len[5]==b.len[(i+1)%6])
           return true;//固定a, 逆时针比較
    }
    return false;
}

int main()
{
    int n;
    scanf("%d",&n);
    SnowFlake sf;
    while(n--)
    {
        for(int i=0;i<6;i++)
            scanf("%d",&sf.len[i]);
        Hash(sf);
    }
    for(int i=0;i<prime;i++)
        if(hs[i].size()>1)//有可能有同样的雪花
    {
        for(int j=0;j<hs[i].size();j++)
            for(int k=j+1;k<hs[i].size();k++)
        {
            if(cmp(hs[i][j],hs[i][k]))
            {
                printf("Twin snowflakes found.");
                return 0;
            }
        }
    }
    printf("No two snowflakes are alike.");
    return 0;
}