一、题解方法
此题不能采用暴力枚举的办法,利用哈希表先将输入数据分类,然后针对key值相同的雪花,再进一步进行细致地判断。
key值采取雪花6个arm值加和,进行粗略比较,因为只有在key值相同的前提下,才有可能两个雪花完全一致。如果两个雪花key值相同,再分别比较每一个arm的长度,顺时针、逆时针比较判断二者异同。
只要发现存在相同的雪花,就返回结果。
二、题解代码
1 #include "stdio.h" 2 #include "stdlib.h" 3 #include <iostream> 4 #include "string.h" 5 #include "math.h" 6 7 using namespace std; 8 9 const int PRIME = 14997; 10 11 12 typedef struct 13 { 14 int arm[6]; 15 16 }leaves; 17 18 int hash_table[PRIME+3]; 19 leaves snow[PRIME+3][100]; 20 21 int getkey(leaves l) 22 { 23 int i; 24 int key = 0; 25 for (i = 0; i < 6; i++) 26 { 27 key += l.arm[i]; 28 } 29 key %= PRIME; 30 return key; 31 } 32 33 int cmp(leaves x, leaves y) 34 { 35 int st, i, j; 36 for (st = 0; st < 6; st++){ 37 for (i = st, j = 0; j < 6; j++, i = (i + 1) % 6){ 38 if(x.arm[i] != y.arm[j]) break; 39 } 40 if(j == 6) return 1; 41 } 42 for (st = 0; st < 6; st++) 43 { 44 for (i = st, j = 0; j < 6; j++, i = (i + 5) % 6){ 45 if(x.arm[i] != y.arm[j]) break; 46 } 47 if(j == 6) return 1; 48 } 49 return 0; 50 } 51 52 int main() 53 { 54 int n; 55 56 scanf("%d", &n); 57 memset(hash_table, 0, sizeof(hash_table)); 58 while(n--) 59 { 60 int i, pos; 61 leaves leaf; 62 for(i = 0; i < 6; i++) 63 { 64 scanf("%d", &leaf.arm[i]); 65 } 66 pos = getkey(leaf); 67 for(i = 0; i < hash_table[pos]; i++) 68 { 69 if(cmp(leaf, snow[pos][i])){ 70 printf("Twin snowflakes found."); 71 return 0; 72 } 73 } 74 snow[pos][hash_table[pos]] = leaf; 75 hash_table[pos]++; 76 } 77 printf("No two snowflakes are alike."); 78 return 0; 79 }