本文主要是介绍POJ 3349 Snowflake Snow Snowflakes hash，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：每个雪花有六个角，每个角用一个数字表示。输入n个雪花，若存在两个雪花相等则输出Twin snowflakes found。否则输出No two snowflakes are alike.
题解：hash
#include <iostream>
#include <cstdlib>
using namespace std;#define Prime 14997struct ListNode
{int a[6];struct ListNode *next;
};
struct ListNode table[Prime];bool isFindsame( int key, int *b )
{ListNode *p = table[key].next;int i, j, cnt, s;while( p != NULL ){for( s = 0; s < 6; ++s ) /*枚举比较的起点，一个始终0-5，另一个不断改变*/{for( i = cnt = 0, j = s; cnt < 6; ++i,++j ) //顺时针{if ( j > 5 ) j = j % 6;if( p->a[i] != b[j] ) break;else ++cnt;}if( cnt == 6 ) return true; /*若六个角均相同，则返回true*/for( i = cnt = 0, j = s; cnt < 6; ++i, --j ) //逆时针{if ( j < 0 ) j = j + 6;if( p->a[i] != b[j] ) break;else ++cnt;}if( cnt == 6 ) return true;}p = p->next;}return false;
}void Insert( int key, int *b )
{ListNode *p = new (ListNode);for ( int i = 0; i < 6; ++i )p->a[i] = b[i];p->next = table[key].next;table[key].next = p;
}int main()
{int b[6], n, HashVal, id, i, j;bool flag = false;memset(table,NULL,sizeof(table));scanf("%d",&n);for( i = 0; i < n && !flag; i++ ){for( j = HashVal = 0; j < 6; j++ ){scanf("%d",b+j);HashVal += b[j];}id = HashVal % Prime;if( isFindsame( id, b ) ) flag = true;else Insert( id, b );}if( flag )printf("Twin snowflakes found.\n");elseprintf("No two snowflakes are alike.\n");return 0;
}
这篇关于POJ 3349 Snowflake Snow Snowflakes hash的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
