POJ 3349 Snowflake Snow Snowflakes （哈希表）-白红宇

POJ 3349 Snowflake Snow Snowflakes （哈希表）

阅读量：4955 次

发布时间：2019-06-12

本文共 1458 字，大约阅读时间需要 4 分钟。

题意：每片雪花有六瓣，给出n片雪花，六瓣花瓣的长度按顺时针或逆时针给出，判断其中有没有相同的雪花（六瓣花瓣的长度相同）

思路：如果直接遍历会超时，我试过。这里要用哈希表，哈希表的关键码key用六瓣花瓣的长度的和取余一个数得到，表中为雪花的存储位置address（即在snowflakes数组中的位置）

代码：

#include
    
     #include
     
      using namespace std;const int maxn=100000+100;//雪花最多数目const int mo=98765;//哈希取余的数int snowflakes[maxn][6];//存储雪花信息vector
      
       hash[mo];//哈希表bool issame(int a,int b){	for(int j=0;j<6;j++)  	{  		if(/*顺时针方向*/  			(snowflakes[a][0] == snowflakes[b][j] &&  			snowflakes[a][1] == snowflakes[b][(j+1)%6] &&  			snowflakes[a][2] == snowflakes[b][(j+2)%6] &&  			snowflakes[a][3] == snowflakes[b][(j+3)%6] &&  			snowflakes[a][4] == snowflakes[b][(j+4)%6] &&  			snowflakes[a][5] == snowflakes[b][(j+5)%6])  						||  			/*逆时针方向*/  			(snowflakes[a][0] == snowflakes[b][j] &&  			snowflakes[a][1] == snowflakes[b][(j+5)%6] &&  			snowflakes[a][2] == snowflakes[b][(j+4)%6] &&  			snowflakes[a][3] == snowflakes[b][(j+3)%6] &&  			snowflakes[a][4] == snowflakes[b][(j+2)%6] &&  			snowflakes[a][5] == snowflakes[b][(j+1)%6])  			)  			return true;	}	return false;}int main(){	int n;	bool exist=false;	while(scanf("%d",&n)!=EOF)	{		int i,j,k;		for(i=0;i

::iterator it; for(it=hash[key].begin();it!=hash[key].end();it++)//遍历哈希表中key相同的雪花 if(issame(*it,i)) { exist=true; break; } hash[key].push_back(i); } if(exist) printf("Twin snowflakes found.\n"); else printf("No two snowflakes are alike.\n"); } return 0;}

转载于:https://www.cnblogs.com/bofengyu/p/4477416.html

你可能感兴趣的文章