poj 3349hash

题意：判断有没有两朵相同的雪花。每朵雪花有六瓣，比较花瓣长度的方法看是否是一样的，如果对应的arms有相同的长度说明是一样的。给出n朵，只要有两朵是一样的就输出有Twin snowflakes found.，如果任何两个都是不一样的输出No two snowflakes are alike。n=100,000。

思路：最简单的就是枚举每两片雪花，判断他们是否相同。时间复杂度为O(n*n)，显然效果不理想。有没有更好的算法呢？hash：每读进一片雪花，将雪花hash，判断hash表里是否有相同的hash值，有相同的hash值，从链表中一一取出并判断是否同构，是同构得出结果。然后将该雪花加入到表中，所有雪花读完也没有发现相同的，则得出结果。

代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <iostream>
using namespace std;

const int MAX_SIZE = 100005; //最大的雪花数
const int MOD_VAL = 90001; //hash函数，取余的数

int snow[MAX_SIZE][6]; //存储雪花信息
vector<int> hash[MOD_VAL]; //hash表，表中存储的是snow数组的下标

						   /*判断雪花a与雪花b是否同样
						   *输入：两个雪花在snow数组的下标
						   *输出：true or false
*/
bool isSame(int a, int b) 
{
    for(int i=0;i<6;i++)
    {
        if(/*顺时针方向*/
			(snow[a][0] == snow[b][i] &&
			snow[a][1] == snow[b][(i+1)%6] &&
			snow[a][2] == snow[b][(i+2)%6] &&
			snow[a][3] == snow[b][(i+3)%6] &&
			snow[a][4] == snow[b][(i+4)%6] &&
			snow[a][5] == snow[b][(i+5)%6])
			
			||
            /*逆时针方向*/
			(snow[a][0] == snow[b][i] &&
            snow[a][1] == snow[b][(i+5)%6] &&
            snow[a][2] == snow[b][(i+4)%6] &&
            snow[a][3] == snow[b][(i+3)%6] &&
            snow[a][4] == snow[b][(i+2)%6] &&
            snow[a][5] == snow[b][(i+1)%6])
			)
			
			return true;
    }
	
    return false;
}

int main()
{
    /*处理输入*/
    int n;
	int i,j;
    scanf("%d", &n);
    for( i = 0; i < n; i++) 
	{
        for( j = 0; j < 6; j++)
		{
            scanf("%d", &snow[i][j]);
        }
    }
	
    /*分别处理这n个雪花，判断有没两个雪花是相同的*/
    int sum, key;
    for(i = 0; i < n; i++) 
	{
        /*求出雪花六个花瓣的和*/
        sum = 0;
        for( j = 0; j < 6; j++) 
		{
            sum += snow[i][j];
        }
		
        key = sum % MOD_VAL; //求出key
		
        /*判断在hash表中hash[key]存储的雪花是否与雪花i相同*/
        for(vector<int>::size_type j = 0; j < hash[key].size(); j++) 
		{
            /*若相同，则直接输出，并结束程序*/
            if(isSame(hash[key][j], i))
			{
                printf("%s/n", "Twin snowflakes found.");
                exit(0);
            }
        }
        /*若key相同的雪花没有一个与雪花i相同*/
        hash[key].push_back(i);
    }
	
    /*若都不相同*/
    printf("%s/n", "No two snowflakes are alike.");
	
    return 0;
}

 

 

 关于hash表的题目未完待续……