相应POJ题目：点击打开链接

Description

Input

Output

Sample Input

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

Sample Output

Twin snowflakes found.

题意：

一片雪花有6片叶子，给出n片雪花，下面每行6个数字。分别代表每片叶子长度。问是否存在有2片雪花形态是同样的。

形态同样的定义：例如以下图，2 3 4 5 6 1 和 4 5 6 1 2 3 和 3 2 1 6 5 4 都是形态同样的雪花，即是同一片雪花。

即是一片雪花能够从某一个数開始顺时针或逆时针数。

思路：

把一片雪花的全部长度相加 mod 一个大质数（100w左右）作为键值key，那就仅仅有key同样的雪花才有可能是形态同样的。

而key同样的雪花会映射到哈希表的同一个槽，那我们用链表把key值同样的在同一个槽连起来。仅仅有key相等的时候就一个个比較key值那条链的雪花是否存在形态同样的，假设有就标记，以后就仅仅是读入数据不比較；假设没有就把雪花增加链表。

也能够採用开方性寻址的方法。思路是一样的。比較雪花形态是否相等要分顺时针和逆时针

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <algorithm>
#include <map>
#include <iostream>
using namespace std;
#define N 100007
const int prime = 999983;

typedef struct
{
	int key;
	int arm[7];
}Point;

Point *slot[prime+10];

bool Check(Point *p, Point *q) //p是新的，q是旧的
{
	int i, j;
	//顺时针
	for(j = 0; j < 6; j++){
		for(i = 0; i < 6; i++)
			if(q->arm[i] != p->arm[(i+j)%6]) break;
		if(6 == i) return true;
	}
	//逆时针
	for(j = 0; j < 6; j++){
		for(i = 0; i < 6; i++){
			if(q->arm[i] != p->arm[(12-i-j)%6]) break;
		}
		if(6 == i) return true;
	}
	return false;
}

int Hash(int k)
{
	/*
	char s[20];
	sprintf(s, "%d", k);
	int i, h = 0, a = 232;
	for(i = 0; i < strlen(s); i++)
		h = (a * h + s[i] - ‘0‘) % prime;
		*/
	return (k<<2);
}

bool Try_to_insert(Point *p)
{
	int k = p->key;
	if(NULL == slot[k]){ //有空槽
		slot[k] = p;
		return true;
	}
	while(slot[k])
	{
		if(Check(p, slot[k])) return false;
		k = (k + Hash(k)) % prime;
	}
	slot[k] = p;
	return true;
}

int main()
{
	//freopen("in.txt","r",stdin);
	int i, j, n, flag = 0;
	Point *p;
	scanf("%d", &n);
	for(i = 0; i < n; i++){
		p = (Point *)malloc(sizeof(Point));
		p->key = 0;
		for(j = 0; j < 6; j++){
			scanf("%d", &p->arm[j]);
			p->key = (p->key + p->arm[j]) % prime;
		}
		if(flag) continue;
		if(!Try_to_insert(p)) flag = 1;
	}
	if(flag) printf("Twin snowflakes found.\n");
	else printf("No two snowflakes are alike.\n");
	return 0;
}