Cod sursa(job #575072)

Utilizator rootsroots1 roots Data 7 aprilie 2011 21:11:40
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <stdio.h>

#define MAX 22505

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

int M,N,sol;

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

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

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

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

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

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

inline 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;
		need[i]=0;
	}

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

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

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

	return 0;
}