Cod sursa(job #71137)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 9 iulie 2007 13:35:13
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include<stdio.h>
struct nod
{
	int cam;
	nod *next;
};
nod *prim[22501],*ultim[22501],*ppp;
int q[22501],m,n,k,pq,uq,u[22501],i,a[22501],x,y,z,sol;
void adlist(int ai,int ii);
int main()
{
	FILE *f,*g;
	f=fopen("castel.in","r");
	g=fopen("castel.out","w");
	fscanf(f,"%d%d%d",&m,&n,&k);
	q[1]=k;pq=1,uq=1;
	for(i=1;i<=m*n;i++)
	 fscanf(f,"%d",&a[i]);
	while(pq<=uq)
	{
		x=q[pq];
		pq++;
		u[a[x]]=1;
		ppp=prim[x];
		while(ppp)
		{
			z=ppp->cam;
			if(!u[z])
			{ u[z]=1;
			  uq++;
			  q[uq]=z;
			}
			ppp=ppp->next;
		}
		if(x>n)
		{  y=x-n;
		   if(u[y]==0)
		   {  if(u[a[y]])
		      { u[y]=1;
			uq++;
			q[uq]=y;
		      }
		      else
		      adlist(a[y],y);
		   }
		}
		if(x+n<=n*m)
		{  y=x+n;
		   if(u[y]==0)
		   {  if(u[a[y]])
		      { u[y]=1;
			uq++;
			q[uq]=y;
		      }
		      else
		      adlist(a[y],y);
		   }
		}
		if(x%n!=1)
		{  y=x-1;
		   if(u[y]==0)
		   {  if(u[a[y]])
		      { u[y]=1;
			uq++;
			q[uq]=y;
		      }
		      else
		      adlist(a[y],y);
		   }
		}
		if(x%n!=0)
		{  y=x+1;
		   if(u[y]==0)
		   {  if(u[a[y]])
		      { u[y]=1;
			uq++;
			q[uq]=y;
		      }
		      else
		      adlist(a[y],y);
		   }
		}
	}
	for(i=1;i<=n*m;i++)
	sol+=u[i];
	fprintf(g,"%d\n",sol);
	fcloseall();
	return 0;
}
void adlist(int ai,int ii)
{
	nod *pp;
	if(!prim[ai])
	{  pp=new nod;
	   pp->cam=ii;
	   pp->next=0;
	   prim[ai]=pp;
	   ultim[ai]=pp;
	}
	else
	{
	  pp=new nod;
	  pp->cam=ii;
	  pp->next=0;
	  ultim[ai]->next=pp;
	  ultim[ai]=pp;
	}
}