2526092_wa.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 t, mark, a[6];

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

	if(t)
	{
		for(i = t; i < t+6; i++)
			b[i-t] = a[i%6];
	}
	c[0] = a[0] = b[0];
	for(i = 0; i < 6; i++)
		a[i] = b[i];
	for(j = 1,i = 5; i > 0; i--,j++)
		c[j] = b[i];
	for(i = 1; i < 6; i++)
	{
		if(b[i]<c[i])
		{
			for(i = 0; i < 6; i++)
				a[i] = b[i];
			return ;
		}
		else
			if(b[i]>c[i])
			{
				for(i = 0; i < 6; i++)
					a[i] = c[i];
				return ;
			}
	}
}

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;
}

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