Cod sursa(job #198776)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 14 iulie 2008 17:16:55
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
#include <cstdio>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define N_MAX 151*151
#define IN "castel.in"
#define OUT "castel.out"

int OK=1,N,M,K;
int v[N_MAX];
char E[N_MAX],O[N_MAX],chei[N_MAX],open[N_MAX][4];
int stv[N_MAX];

void scan()
{
	freopen(IN, "r",stdin);
	freopen(OUT, "w",stdout);
	scanf("%d%d%d", &M,&N,&K);
	FOR(i,1,N*M)
		scanf("%d", &v[i]);
	chei[K] = 1;
	stv[0] = 1;
	stv[1] = K;
	E[K] = 1;
}

inline int ok(int x,int y,int t)
{
	if( !(y%N) && t==3)
		return 0;
	if( y%N == 1 && t==4)	
		return 0;
	if(x > 0 && x <= N*M)
		return 1;
	return 0;
}

void try_all(int nod)
{
	int aux;
	aux = nod + N;
	if(ok(aux,nod,1))
	{
		if(!E[aux] && chei[ v[ aux ] ])
		{
			open[nod][1] = 1;
			open[aux][2] = 1;
			E[aux] = 1;
			stv[ ++stv[0] ] = aux;
			chei[ aux ] = 1;
			OK = 1;
			try_all(aux);
		
		}
	}
	else
		open[nod][1] = 1;
	
	aux = nod - N;	
	if(ok(aux,nod,2))
	{
		if(!E[aux] && chei[ v[ aux ] ])
		{
			open[nod][2] = 1;
			open[aux][1] = 1;
			E[aux] = 1;
			stv[ ++stv[0] ] = aux;
			chei[ aux ] = 1;
			OK = 1;
			try_all(aux);
		}
	}
	else
		open[nod][2] = 1;
		
	aux = nod + 1;	
	if(ok(aux,nod,3))
	{
		if(!E[aux] && chei[ v[ aux ] ])
		{
			open[nod][3] = 1;
			open[aux][4] = 1;
			E[aux] = 1;
			stv[ ++stv[0] ] = aux;
			chei[ aux ] = 1;
			OK = 1;
			try_all(aux);
		}
	}	
	else
		open[nod][3] = 1;
		
	aux = nod - 1;
	if(ok(aux,nod,4))
	{
		if(!E[aux] && chei[ v[ aux ] ])
		{
			open[nod][4] = 1;
			open[aux][3] = 1;
			E[aux] = 1;
			stv[ ++stv[0] ] = aux;
			chei[ aux ] = 1;
			OK = 1;
			try_all(aux);
		}
	}	
	else
		open[nod][4] = 1;
	if(open[nod][1] && open[nod][2] && open[nod][3] && open[nod][4])
		O[nod] = 1;
}

void solve()
{
	while(OK)
	{
		OK = 0;
		FOR(i,1,stv[0])
			if(!O[stv[i]] )
				try_all(stv[i]);
	}			
	printf("%d\n", stv[0]);	
}

int main()
{
	scan();
	solve();
	return 0;
}