POJ-3349 Snowflake Snow Snowflakes---最小表示法

题目链接：

https://vjudge.net/problem/POJ-3349

题目大意：

每个雪花都有六个分支，用六个整数代表，这六个整数是从任意一个分支开始，朝顺时针或逆时针方向遍历得到的。输入多个雪花，判断是否有形状一致的雪花存在。

比如输入的是1 2 3 4 5 6，

则2 3 4 5 6 1，3 4 5 6 1 2，……，6 5 4 3 2 1，5 4 3 2 1 6等都是相同形状的。

解题思路：

这里用到了最小表示法的思想，将输入的6个数字依次顺推和逆推，求出最小表示法（可以理解成字典序最小），然后排一下序，判断有没有相邻的相等。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 using namespace std;
 6 const int maxn = 100000 + 10;
 7 const int INF = 0x3f3f3f3f;
 8 struct snow
 9 {
10     int a[6];
11     bool operator <(const snow& b)const
12     {
13         int i = 0;
14         while(a[i] == b.a[i] && i < 6)i++;
15         return i != 6 && a[i] < b.a[i];
16     }
17     bool operator == (const snow& b)const
18     {
19         int i = 0;
20         while(a[i] == b.a[i] && i < 6)i++;
21         return i == 6;
22     }
23     snow(int b[])
24     {
25 
26         snow tmp;
27         memset(a, INF, sizeof(a));
28         for(int start = 0; start < 6; start++)
29         {
30             for(int j = 0; j < 6; j++)//顺
31                 tmp.a[j] = b[(start + j) % 6];
32             if(tmp < *this)*this = tmp;//最小表示
33 
34             for(int j = 0; j < 6; j++)//逆
35                 tmp.a[j] = b[(start - j + 6) % 6];
36             if(tmp < *this)*this = tmp;//最小表示
37         }
38     }
39     snow(){}
40 }s[maxn];
41 int main()
42 {
43     int n, a[6];
44     scanf("%d", &n);
45     for(int i = 0; i < n; i++)
46     {
47         for(int j = 0; j <6; j++)
48             scanf("%d", &a[j]);
49         s[i] = snow(a);
50     }
51     sort(s, s + n);
52     bool ok = 0;
53     for(int i = 0; i < n - 1; i++)
54     {
55         if(s[i] == s[i + 1])
56         {
57             ok = 1;
58             break;
59         }
60     }
61     if(ok)cout<<"Twin snowflakes found."<<endl;
62     else cout<<"No two snowflakes are alike."<<endl;
63     return 0;
64 }