Cod sursa(job #472686)

Utilizator borsoszalanBorsos Zalan borsoszalan Data 26 iulie 2010 12:03:50
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <stdio.h>
#define N 155
int dlin[]={0,0,-1,1};
int dcol[]={1,-1,0,0};
struct bfs
{
	int a,b;
};
bfs coada[N*N];
int m,n,k,v[N][N],r,rez;
char marc[N][N],cheie[N*N];
void read()
{
	scanf("%d%d%d",&m,&n,&k);
	int i,j;
	for (i=1; i<=m; i++)
		for (j=1; j<=n; j++)
			scanf("%d",&v[i][j]);
	cheie[k]=1;
	if (k%n==0)
	{
		coada[++r].a=k/n;
		coada[r].b=n;
	}
	else
	{
		coada[++r].a=k/n+1;
		coada[r].b=k-(k/n*n);
	}
	rez=1;
	marc[coada[r].a][coada[r].b]=1;
}
void bordare()
{
	int i;
	for (i=0; i<=m+1;i++)
	{
		marc[i][0]=1;
		marc[i][n+1]=1;
	}
	for (i=0; i<=n+1; i++)
	{
		marc[0][i]=1;
		marc[m+1][i]=1;
	}
}
void bfs()
{
	int ant=0,act,ok=1,i,j,x,y;
	bordare();
	while (ok)
	{
		act=r;
		ok=0;
		for (i=ant+1; i<=act; i++)
			for (j=0; j<4; j++)
			{
				x=coada[i].a+dlin[j];
				y=coada[i].b+dcol[j];
				if (!marc[x][y] && cheie[v[x][y]])
				{
					coada[++r].a=x;
					coada[r].b=y;
					marc[x][y]=1;
					ok=1;
					cheie[n*(x-1)+y]=1;
					rez++;
				}
			}
		if (!ok)
		{
			for (i=1; i<=r; i++)
				for (j=0; j<4; j++)
				{
					x=coada[i].a+dlin[j];
					y=coada[i].b+dcol[j];
					if (!marc[x][y] && cheie[v[x][y]])
					{
						coada[++r].a=x;
						coada[r].b=y;
						marc[x][y]=1;
						ok=1;
						cheie[n*(x-1)+y]=1;
						rez++;
					}
				}
		}
		ant=act;
	}
}
int main()
{
	freopen("castel.in","r",stdin);
	freopen("castel.out","w",stdout);
	read();
	bfs();
	printf("%d\n",rez);
	return 0;
}