Cod sursa(job #198485)

Utilizator AndreyPAndrei Poenaru AndreyP Data 11 iulie 2008 18:47:07
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include<stdio.h>
int n,m,k,max,r;
int castel[25000];
struct graf
{
	int nod;
	graf *next;
};
graf *a[25000];
bool viz[25000];
void citire()
{
	scanf("%d%d%d",&n,&m,&k);
	max=n*m+1;
	for(int i=1; i<max; i++)
		scanf("%d",&castel[i]);
}
void adauga(int unde,int cine)
{
	graf *g=new graf;
	g->nod=cine;
	g->next=a[unde];
	a[unde]=g;
}
void bfs()
{
	int c[30001];
	const int d[]={-m,1,m,-1};
	int inc=0,sf=0,now,next,i;
	c[0]=k;
	graf *g;
	r=1;
	viz[k]=true;
	while(inc<=sf)
	{
		now=c[inc++];
		g=a[now];
		while(g)
		{
			if(!viz[g->nod])
			{
				viz[g->nod]=true;
				c[++sf]=g->nod;
				r++;
			}
			g=g->next;
		}
		for(i=0; i<4; i++)
		{
			next=now+d[i];
			if((i==1)&&(now%m==0))
				continue;
			if((i==3)&&(now%m==1))
				continue;
			if((next>0)&&(next<max))
			{
				if(!viz[next])
				{
					if(viz[castel[next]])
					{
						viz[next]=true;
						c[++sf]=next;
						r++;
					}
					else
						adauga(castel[next],next);
				}
			}
		}
	}
}
int main()
{
	freopen("castel.in","r",stdin);
	freopen("castel.out","w",stdout);
	citire();
	bfs();
	printf("%d\n",r);
	return 0;
}