世界上沒(méi)有兩片完全相同的雪花，本題要判斷是否有兩片雪花完全相同。
題中對(duì)雪花進(jìn)行了簡(jiǎn)化，只是簡(jiǎn)單的將雪花的六個(gè)臂長(zhǎng)作為數(shù)據(jù)，如果進(jìn)一步根據(jù)分形學(xué)抽象雪花的話，那么題目的難度會(huì)有所增加。
由于數(shù)據(jù)的規(guī)模很大，所以如何比較兩片雪花是關(guān)鍵。很自然的選擇提取雪花的特征，所以應(yīng)該根據(jù)六個(gè)臂長(zhǎng)設(shè)計(jì)它的特征，該特征量設(shè)計(jì)的好壞是程序效率的主要因素。
本解法先簡(jiǎn)單的將各個(gè)臂長(zhǎng)乘以一個(gè)系數(shù)并相加作為雪花的特征值，然后將該特征值作為散列值加入到表中，最后查找是否有相同的雪花存在。
#include <cstdio>
const int SNOWNUM = 100005;
const int HASHSIZE = 1000000;
struct staticList{
int data[6];
int next;
};
staticList sList[SNOWNUM];
int newNode;
int nHashIndex[HASHSIZE+5];
int main()
{
int i,j;
int num;
bool suc;
int tmp[6],data[6];
scanf("%d",&num);
for(i=0; i<num; ++i)
sList[i].next = -1;
for(i=0; i<HASHSIZE; ++i)
nHashIndex[i] = -1;
newNode = 0;
suc = false;
for(i=0; i<num; ++i)
{
int nClockSt = 0, nClockVa = 0, nClockVaTemp = 0;
int nCountSt = 0, nCountVa = 0, nCountVaTemp = 0;
for(j=0; j<6; ++j)
scanf("%d",&tmp[j]);
for(j=0; j<6; ++j)
{
nClockVaTemp = tmp[j] * 6 + tmp[(j+1)%6] * 5 + tmp[(j+2)%6] * 4 + tmp[(j+3)%6] * 3 + tmp[(j+4)%6] * 2 + tmp[(j+5)%6];
if(nClockVa < nClockVaTemp) {nClockVa = nClockVaTemp; nClockSt = j;}
nCountVaTemp = tmp[j] * 6 + tmp[(j+5)%6] * 5 + tmp[(j+4)%6] * 4 + tmp[(j+3)%6] * 3 + tmp[(j+2)%6] * 2 + tmp[(j+1)%6];
if(nCountVa < nCountVaTemp) {nCountVa = nCountVaTemp; nCountSt = j;}
}
if(nClockVa > nCountVa)
{
for(j=0; j<6; ++j)
data[j] = tmp[(nClockSt+j)%6];
}
else
{
for(j=0; j<6; ++j)
data[j] = tmp[(nCountSt+6-j)%6];
}
int nValue = nClockVa > nCountVa ? nClockVa : nCountVa;
nValue %= HASHSIZE;
if(nHashIndex[nValue] != -1)
{
int next = nHashIndex[nValue];
while(next != -1)
{
for(j=0; j<6; ++j)
if(data[j] != sList[next].data[j]) break;
if(j==6)
{
suc = true;
goto en;
}
next = sList[next].next;
}
for(j=0; j<6; ++j)
sList[newNode].data[j] = data[j];
sList[newNode].next = nHashIndex[nValue];
nHashIndex[nValue] = newNode;
++newNode;
}
else
{
for(j=0; j<6; ++j)
sList[newNode].data[j] = data[j];
nHashIndex[nValue] = newNode;
++newNode;
}
}
en: if(suc)
{
for(++i; i<num; ++i)
{
for(j=0; j<6; ++j)
scanf("%d",&tmp[j]);
}
}
if(suc)
printf("Twin snowflakes found.\n");
else
printf("No two snowflakes are alike.\n");
return 0;
}