首页 > 代码库 > Hash poj3349 Snowflake Snow Snowflakes

Hash poj3349 Snowflake Snow Snowflakes

2024-07-06 12:21:23   225人阅读

题意：判断是否有两片一样的雪花。 Hash第一题，基本是抄的。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <string>
#include <iostream>
using namespace std;
char str[]={"No two snowflakes are alike."};
char str1[]={"Twin snowflakes found."};
const int INF= 9997;
struct Node
{
    int a[6];int hash_val;
}node [INF][10];
 
int len[INF];
 
int get_hash(Node & a)
{
    a.hash_val=0;
    for(int i=0;i<6;i++)
        a.hash_val+=a.a[i];
    return a.hash_val %= INF;
}
 
int match(Node a,Node b)
{
    int cw=0;int ancw=0;
    for(int i=0;i<6;i++){
        if(a.a[0]==b.a[i]){
            int cw=1;int ancw=1;
            for(int j=1;j<6;j++){
                if(a.a[j]!=b.a[(i+j)%6]){
                    cw=0;
                }
            }
            for(int j=1;j<6;j++){
                if(a.a[j]!=b.a[(i-j+6)%6]){
                    ancw=0;
                }
            }
            if(cw||ancw)
                return 1;
        }
    }
    return 0;
}
 
int find_hash(Node a)
{
    int val=a.hash_val;
    for(int i=0;i<len[val];i++){
        if(match(a,node[val][i]))
            return 1;
    }
    return 0;
}
 
int main()
{
    Node node1;
    int flag=0;
    int n;
    scanf("%d",&n);
    memset(len,0,sizeof(len));
    while(n--){
        for(int i=0;i<6;i++)
            scanf("%d",&node1.a[i]);
        int val=get_hash(node1);
        if(flag)
            continue;
        if(find_hash(node1))
            flag=1;
        node[val][len[val]++]=node1;
        //printf("%d ",len[val]);
    }
    if(flag){
        printf("%s\n",str1);
    }
    else
        printf("%s\n",str);
    return 0;
}

　　


联系
我们