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

题目链接：

题目大意：

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

比如输入的是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个数字依次顺推和逆推，求出最小表示法（可以理解成字典序最小），然后排一下序，判断有没有相邻的相等。

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 using namespace std;

 const int maxn =  + ;

 const int INF = 0x3f3f3f3f;

 struct snow

 {

     int a[];

     bool operator <(const snow& b)const

     {

         int i = ;

         while(a[i] == b.a[i] && i < )i++;

         return i !=  && a[i] < b.a[i];

     }

     bool operator == (const snow& b)const

     {

         int i = ;

         while(a[i] == b.a[i] && i < )i++;

         return i == ;

     }

     snow(int b[])

     {

         snow tmp;

         memset(a, INF, sizeof(a));

         for(int start = ; start < ; start++)

         {

             for(int j = ; j < ; j++)//顺

                 tmp.a[j] = b[(start + j) % ];

             if(tmp < *this)*this = tmp;//最小表示

             for(int j = ; j < ; j++)//逆

                 tmp.a[j] = b[(start - j + ) % ];

             if(tmp < *this)*this = tmp;//最小表示

         }

     }

     snow(){}

 }s[maxn];

 int main()

 {

     int n, a[];

     scanf("%d", &n);

     for(int i = ; i < n; i++)

     {

         for(int j = ; j <; j++)

             scanf("%d", &a[j]);

         s[i] = snow(a);

     }

     sort(s, s + n);

     bool ok = ;

     for(int i = ; i < n - ; i++)

     {

         if(s[i] == s[i + ])

         {

             ok = ;

             break;

         }

     }

     if(ok)cout<<"Twin snowflakes found."<<endl;

     else cout<<"No two snowflakes are alike."<<endl;

     return ;

 }

巴特西

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

最新文章

热门文章