poj3349SnowflakeSnowSnowflakes

发表于: 2013年01月21 00:00

已知一片雪花的有6个角,给你一些数据,分别表示一片雪花的每个角的长度. 然后你要找出是否存在两片相同的雪花. 如果两片雪花,角的长度按照次序对应相等,则可以说它们是相同的.例如

1 2 3 4 5 6

4 3 2 1 6 5 可以从1逆时针看 所以这是两片相同的雪花

###做法

先用hash把数据存一下,计算时对于hash值相同的雪花.固定一片雪花,另一片雪花,我们分别按逆时针和顺时针的顺序去 和前面的一片雪花去对比角的长度.

这是做的第一道hash题.代码写的不够简介. :::c++

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define PRE 999983
#define VIS 1
int check(int ,int *);
bool state;
struct node
{
    int inf[6];
    struct node *next;
};
struct myhash
{
    bool state;//这个成员是不必要的
    struct node *link;
}myhash[PRE+10];

int main()
{
    int n,tt[6],key,j;
    state=false;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        key=0;
        for(j=0;j<6;j++)
        {
            scanf("%d",&tt[j]);
            key+=tt[j]%PRE;
        }
        if(!state)
            check(key,tt);
    }
    if(state)
        printf("Twin snowflakes found.\n");
    else
        printf("No two snowflakes are alike.\n");
}
int check(int key,int *arr)
{   bool ok=true;
    key%=PRE;
    if(!myhash[key].state)
    {
        myhash[key].state=true;
        myhash[key].link=(struct node *)malloc(sizeof(struct node));
        myhash[key].link->next=NULL;
        for(int i=0;i<6;i++)
            myhash[key].link->inf[i]=arr[i];
        return 0;
    }
    struct node *p=myhash[key].link;
    struct node *pr=p;
//  printf("p=%p   p->next=%p\n",p,p->next);
    while(p!=NULL)
    {
        for(int k=0;k<6 && !state;k++)
        {
            ok=true;
            for(int i=0;i<6;i++)
                if(p->inf[i]!=arr[(i+k)%6])
                        ok=false;
            if(ok) state=true;
        }
        for(int k=0;k<6 && !state;k++)
        {
            ok=true;
            for(int i=0;i<6;i++)
            {
                if(p->inf[i]!=arr[(k-i+6)%6])
                    ok=false;
            }
            if(ok) state=true;
        }
        pr=p;
        p=p->next;
    }
    if(!state)
    {
        p=(struct node *)malloc(sizeof(struct node));
        p->next=NULL;
        for(int i=0;i<6;i++)
            p->inf[i]=arr[i];
        pr->next=p;
    }
}
© 2018 - fluyy - 粤ICP备17114935号