http://poj.org/problem?id=3349
题意:
给出n片雪花留个角的长度,要求判断是否有一样的雪花。
思路:
Hash表的应用。
首先将每个雪花所有角的总长计算出来,如果两片雪花相同的话那么总长也是相同的,然后加入vector容器当中,最后遍历vector数组,如果某个总长有大于1的雪花数,则有可能存在相同的雪花,此时需要比较这些雪花。
#include <iostream>
#include <stdio.h>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = ;
const int prime = ; struct node
{
int len[];
}snow; vector<node>hs[prime]; bool judge(node a, node b)
{
for (int i = ; i<; i++)
{
if (a.len[] == b.len[i] && a.len[] == b.len[(i + ) % ] && a.len[] == b.len[(i + ) % ] &&
a.len[] == b.len[(i + ) % ] && a.len[] == b.len[(i + ) % ] && a.len[] == b.len[(i + ) % ])
return true;//固定a,顺时针比较
if (a.len[] == b.len[i] && a.len[] == b.len[(i + ) % ] && a.len[] == b.len[(i + ) % ] &&
a.len[] == b.len[(i + ) % ] && a.len[] == b.len[(i + ) % ] && a.len[] == b.len[(i + ) % ])
return true;//固定a, 逆时针比较
}
return false;
} int main()
{
//freopen("D:\\txt.txt", "r", stdin);
int n;
cin >> n;
while (n--)
{
for (int i = ; i<; i++)
scanf("%d", &snow.len[i]);
int sum = (snow.len[] + snow.len[] + snow.len[] + snow.len[] + snow.len[] + snow.len[]) % prime;
hs[sum].push_back(snow);
}
for (int i = ; i<prime; i++)
if (hs[i].size()>) //可能有相同的雪花
{
for (int j = ; j<hs[i].size(); j++)
for (int k = j + ; k<hs[i].size(); k++)
{
if (judge(hs[i][j], hs[i][k]))
{
printf("Twin snowflakes found.");
return ;
}
}
}
printf("No two snowflakes are alike.");
return ;
}