POJ 3349 Snowflake Snow Snowflakes Hash

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <iostream>
  4 using namespace std;
  5 const int prime = 999983;
  6 
  7 struct Snow
  8 {
  9     int leg[6];
 10 }snow[100000];
 11 
 12 struct HashTable
 13 {
 14     struct Snow *data;
 15     struct HashTable *next;
 16     HashTable()
 17     {
 18         next = NULL;
 19     }
 20 };
 21 
 22 struct HashTable *Hash[prime];
 23 
 24 bool clockwise(const struct Snow &a, const struct Snow &b)
 25 {
 26     for(int i = 0, j; i < 6; i++)
 27     {
 28         if(a.leg[i] == b.leg[0])
 29         {
 30             for(j = 0; j < 6; j++)
 31             {
 32                 if(a.leg[(i+j)%6] != b.leg[j])
 33                     break;
 34             }
 35             if(j >= 6)return 1;
 36         }
 37     }
 38     return 0;
 39 }
 40 
 41 bool counterclockwise(const struct Snow &a, const struct Snow &b)
 42 {
 43     for(int i = 0, j; i < 6; i++)
 44     {
 45         if(a.leg[i] == b.leg[5])
 46         {
 47             for(j = 0; j < 6; j++)
 48             {
 49                 if(a.leg[(i+j)%6] != b.leg[5-j])
 50                     break;
 51             }
 52             if(j >= 6)return 1;
 53         }
 54     }
 55     return 0;
 56 }
 57 
 58 bool hash_insert(int key, struct Snow *snow_ptr)
 59 {
 60     if(Hash[key] == NULL)
 61     {
 62         Hash[key] = new HashTable;
 63         Hash[key]->data = snow_ptr;
 64     }
 65     else
 66     {
 67         struct HashTable *p = Hash[key];
 68         while(p != NULL)
 69         {
 70             if(clockwise(*p->data, *snow_ptr) || counterclockwise(*p->data, *snow_ptr))
 71                 return 1;
 72             else p = p->next;
 73         }
 74         p = new HashTable;
 75         p->data = snow_ptr;
 76     }
 77     return 0;
 78 }
 79 
 80 int main()
 81 {
 82     int n, key;
 83     while(scanf("%d", &n) != EOF)
 84     {
 85         bool ok = 0;
 86         memset(Hash, 0, sizeof(Hash));
 87         for(int i = 0; i < n; i++)
 88         {
 89             key = 0;
 90             for(int j = 0; j < 6; j++)
 91             {
 92                 scanf("%d", &snow[i].leg[j]);
 93                 key += snow[i].leg[j];
 94             }
 95             key %= prime;
 96             if(!ok)
 97             {
 98                 ok = hash_insert(key, &snow[i]);
 99             }
100         }
101         printf("%s
", ok ? "Twin snowflakes found." : "No two snowflakes are alike.");
102     }
103     return 0;
104 }
View Code