poj3349 Snowflake Snow Snowflakes —

题意：雪花有6个瓣，有n个雪花，输入每个雪花的瓣长，判断是否有一模一样的雪花（通过旋转或翻转最终一样，即瓣长对应相等）。如果前面的雪花判断出有重复，则不需对后续的进行操作。

题解：直接将花瓣存在二维数组里面，然后每次新输入一个，再对之前的进行遍历判重。但是这种做法很低效，遍历花了很多时间。所以用哈希表，可直接访问是否存在重复，如果不重复，则用一维数组将雪花存起来（数组包含在结构体里），并将其“挂”在相应的哈希值（key）位置。而key值为6个瓣的总长。所以“挂”在同一key上的雪花有个共同的特点：总瓣长%MAX=key。 MAX为哈希值的个数。整个哈希表由tab[MAX] 和 q[100010]（结构体，记录雪花信息）。

代码如下：

#include<cstdio>//poj3349

#include<cstring>

#define MAX 90001

struct node//记录花瓣信息，“挂在”tab[key]上

{

    int a[12];

    int next;//下一个雪花的地址

}q[100010];

int tab[MAX],cur;//tab[]记录相应key值得第一个雪花

int get(int *b)//获取key值

{

    int sum = 0;

    for(int i = 0; i<6; i++)

        sum += b[i];

    return sum%MAX;

}

void insert(int key, int *b)//挂在tab[key]上，头插法

{

    for(int i = 0; i<6; i++)

        q[cur].a[i] = q[cur].a[i+6] = b[i];

    q[cur].next = tab[key];

    tab[key] = cur++;

}

int search(int key,int *b)

{

    int i,h = tab[key];

    while(h!=-1)

    {

        for(int mov = 0; mov<6; mov++)//旋转的步数

        {

            for(i = 0; i<6; i++)//正面判断

                if(q[h].a[i+mov]!=b[i]) break;

            if(i==6) return 1;

            for(i = 0; i<6; i++)//反面判断，即翻转再正面判断

                if(q[h].a[i+mov]!=b[5-i]) break;

            if(i==6) return 1;

        }

        h = q[h].next;

    }

    insert(key,b);//如果没有重复，则插入

    return 0;

}

int main()

{

    int n,b[6],key,flag = 0;

    scanf("%d",&n);

    cur = 0;

    memset(tab,-1,sizeof(tab));

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

    {

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

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

        if(flag) continue;

        key = get(b);

        if(search(key,b))

            flag = 1;

    }

    if(flag)

        puts("Twin snowflakes found.");

    else

        puts("No two snowflakes are alike.");

    return 0;

}

巴特西

poj3349 Snowflake Snow Snowflakes —— 哈希表

最新文章

热门文章