题目难点在于对两片雪花的比较,哈希可以加快搜索速度,防止超时,而对于如何逆时针和顺时针比较雪花是否相同便成为重点。
在这里给出两条公式:
设i为A、B的第i片叶子,j为B当前顺时针转过的格数
那么 A(i) ---> B( (i+j)%6 )
设i为A、B的第i片叶子,j为B当前逆时针转过的格数
那么 A(i) ---> B( (5-i-j+6)%6 )
#includeusing namespace std;#define mod 999983typedef struct Hashtable { int arm[6]; struct Hashtable * next;}Hashtable;int Hash(int a[]){ int key=0; for (int i = 0; i<6; i++) key += a[i] % mod; return key%mod;}Hashtable hash1[mod];void init(){ for (int i = 0; i next = NULL; for (int x = 0; x<6; x++) node->arm[x] = snow[x]; } else{ node->next = hash1[key].next; hash1[key].next = node; for (int x = 0; x<6; x++) node->arm[x] = snow[x]; Hashtable * p = node; while (p->next != NULL){ p = p->next; a = clock(p->arm, snow); b = opposite(p->arm, snow); if (a || b){ printf("Twin snowflakes found.\n"); return 0; } } } } if (!a&&!b) printf("No two snowflakes are alike.\n"); return 0;}