Cod sursa(job #136275)

Utilizator znakeuJurba Andrei znakeu Data 15 februarie 2008 13:07:38
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <stdio.h>

#define NMMAX 170
int n,m,k;
int w[NMMAX*NMMAX];
int u[NMMAX*NMMAX],q;
int *lst[NMMAX*NMMAX];
int dx[5]={0,1,0,-1};
int dy[5]={1,0,-1,0};

int main()
{
	FILE *in  = fopen("castel.in","r");
	FILE *out = fopen("castel.out","w");
	
	
	int i,j,a,b;
	fscanf(in,"%d%d%d",&n,&m,&k);
	for (i=0; i<n; i++)
		for (j=0; j<m; j++)
		{
			fscanf(in,"%d",&u[i*m+j]);
			u[i*m+j]--;
			w[u[i*m+j]]++;
		}
	for (i=0; i<n*m; i++)
	{
		lst[i]=new int [w[i]+3];
		lst[i][0]=0;
	}
	
	for (i=0; i<n; i++)
		for (j=0; j<m; j++)
		{
			lst[u[i*m+j]][++lst[u[i*m+j]][0]]=i*m+j;			
		}
	
	for (i=0; i<NMMAX*NMMAX; i++)
	{
		w[i]=0;
		u[i]=0;
	}
	k--; w[k]=-2; u[0]=k;	q=1;
	
	for (i=0; i<q; i++)
	{
		a=u[i];
		for (j=1; j<=lst[a][0]; j++)
		{
			if(w[lst[a][j]]==0)
			{
				w[lst[a][j]]=-3;
			}
			if(w[lst[a][j]]==-1)
			{
				w[lst[a][j]]=-2;
				u[q++]=lst[a][j];				
			}
		}
		for (j=0; j<4; j++)
		{
			b=(a/m+dx[j])*m+(a%m+dy[j]);
			if (a/m+dx[j]>=0 && a/m+dx[j]<n && a%m+dy[j]>=0 && a%m+dy[j]<m)
			{
				if (w[b]==0)
				{
					w[b]=-1;
				}
				if (w[b]==-3)
				{
					w[b]=-2;
					u[q++]=b;					
				}
			}
		}
	}	
	fprintf(out,"%d\n",q);
	fclose(in);
	fclose(out);
	return 0;
}