2526472_ac_2041ms_4048k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <stdlib.h>
#define INIT (HASH *)malloc(sizeof(HASH))

typedef struct node
{
	int num[6];
	struct node *l, *r;
}HASH;

HASH *root;

int mark, a[6];

int cmp(int num[])
{
	int i;

	for(i = 0; i < 6; i++)
		if(num[i]<a[i])
			return 1;
		else
			if(num[i]>a[i])
				return -1;
	return 0;
}

void cpy(int b[])
{
	for(int i = 0; i < 6; i++)
		a[i] = b[i];
}

void change(int b[])
{
	int tt;

	tt = b[0];
	for(int i = 1; i < 6; i++)
		b[i-1] = b[i];
	b[5] = tt;
}

void dir(int b[])
{
	int i, tt;

	for(i = 5; i > 3; i--)
	{
		tt = b[6-i];
		b[6-i] = b[i];
		b[i] = tt;
	}
}

void turn()
{
	int i, j;
	int b[6], c[6];

	for(i = 0; i < 6; i++)
		b[i] = c[i] = a[i];
	j = 6;
	while(j--)
	{
		if(cmp(b)==1)
			cpy(b);
		dir(b);
		if(cmp(b)==1)
			cpy(b);
		change(c);
		for(i = 0; i < 6; i++)
			b[i] = c[i];
	}

}



int insert()
{
	int i;
	HASH *p, *q;

	if(mark)
	{
		root = INIT;
		for(i = 0; i < 6; i++)
			root->num[i] = a[i];
		mark = 0;
		root->l = NULL;root->r = NULL;
	}
	else
	{
		p = root;q = INIT;
		for(i = 0; i < 6; i++)
			q->num[i] = a[i];
		q->l = NULL;q->r = NULL;
		while(p)
		{
			int v = cmp(p->num);
			if(v>0)
			{
				if(p->r)
					p = p->r;
				else
				{
					p->r = q;
					break;
				}
			}
			else
				if(v<0)
				{
					if(p->l)
						p = p->l;
					else
					{
						p->l = q;
						break;
					}
				}
				else
					return 1;
		}
	}
	return 0;
}

int main()
{
	int n, i, j, m;

	scanf("%d",&n);
	m = 0;mark = 1;
	for(i = 0; i < n; i++)
	{
		for(j = 0; j < 6; j++)
			scanf("%d",&a[j]);
		if(m)
			continue;
		turn();
		if(insert())
		{
			m = 1;
			printf("Twin snowflakes found.\n");
		}
	}
	if(!m)
		printf("No two snowflakes are alike.\n");
	return 1;
}