| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
2172MS,一次通过好爽!!!附代码其他不多说,说说如何判重的,把两个数组中的一个复制后接在其后面,形成一个长度为12的长数组,然后另一个短数组与其进行匹配,考虑到顺逆时针的问题,需要把短数组逆置一下再匹配一次,如果有一次匹配成功说明是同一片雪花。 请指教!!
#include <stdio.h>
#define M 100003
struct node{
int a[6];
struct node* next;
};
typedef node snowflake;
// 哈希函数
unsigned int hash(int a[]){
int i=0,cnt=0;
for(i=0;i<6;i++){
cnt+=a[i];
}
return cnt%M;
}
// 判重函数
int judge(int a[6],int b[6]){
int c[12]={0};
int i,j,k;
for(i=0;i<6;i++){
c[i]=c[6+i]=a[i];
}
//for(i=0;i<12;i++) printf("%d ",c[i]);
for(i=0;i<=6;i++){
j=0;
for(k=i;k<=(i+5);k++){
if(c[k]==b[j++]) continue;
else break;
}
if(j==6) return 1;
}
return 0;
}
// 逆置函数
int* reverse(int a[6]){
int i;
for(i=0;i<3;i++){
a[i]=a[i]^a[5-i];
a[5-i]=a[5-i]^a[i];
a[i]=a[i]^a[5-i];
}
return a;
}
int main()
{
snowflake* table[M]={NULL};
snowflake* temp;
snowflake snow[M];
int i,j,k,n;
scanf("%d",&n);
for(i=0;i<n;i++){
for(j=0;j<6;j++) scanf("%d",&(snow[i].a[j]));
}
for(i=0;i<n;i++){
k=hash(snow[i].a);
if(table[k]==NULL){
snow[i].next=table[k];
table[k]=&snow[i];
}
else{
temp=table[k];
while(temp!=NULL){
if(judge(temp->a,snow[i].a)==0&&judge(temp->a,reverse(snow[i].a))==0){
temp=temp->next;
}
else{
printf("%s\n","Twin snowflakes found.");
return 0;
}
}
snow[i].next=table[k];
table[k]=&snow[i];
}
}
printf("%s\n","No two snowflakes are alike.");
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator