Cod sursa(job #575062)

Utilizator rootsroots1 roots Data 7 aprilie 2011 21:00:19
Problema Castel Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <stdio.h>

#define MAX 22505

int v[MAX];
char use[MAX];

int M,N,sol;

struct queue
{
	int nod;
	queue *link;
}*key[MAX];

void add(int x,int K)
{
	queue *p;

	p=new queue;
	p->nod=K;
	p->link=key[x];
	key[x]=p;
}

void unlock(int x);
void code(int K);
void crack(int K);

void unlock(int x)
{
	queue *p;
	int K;

	while(key[x]!=NULL)
	{
		K=key[x]->nod;
		p=key[x];
		key[x]=key[x]->link;
		delete p;

		if(v[K]>0)
		{
			use[K]=1;
			v[K]=0;
			sol++;
			unlock(K);
			crack(K);
		}
	}
}

void code(int K)
{
	if(v[K]>0)
		if(use[v[K]])
		{
			use[K]=1;
			v[K]=0;
			sol++;
			unlock(K);
			crack(K);
		}
		else
		add(v[K],K);
}

void crack(int K)
{
	if(K%N!=1) code(K-1);
	if(K%N!=0) code(K+1);
	if(K>N) code(K-N);
	if(K<(M-1)*N) code(K+N);
}

int main()
{
	int i,K;

	freopen("castel.in","r",stdin);

	scanf("%d%d%d",&M,&N,&K);

	for(i=1;i<=M*N;i++)
	{
		scanf("%d",&v[i]);
		use[i]=0;
		key[i]=NULL;
	}

	use[K]=1;
	v[K]=0;
	sol=1;
	crack(K);

	freopen("castel.out","w",stdout);

	printf("%d\n",sol);

	return 0;
}