Mai intai trebuie sa te autentifici.

Cod sursa(job #429061)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 29 martie 2010 19:59:55
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include<cstdio>
const int nmax=1<<8;
bool f[nmax*nmax],ver[nmax][nmax];
int rez,u,n,m,k,cx[nmax*nmax],cy[nmax*nmax],nec[nmax][nmax];
int dl[]={0,1,0,-1};
int dc[]={1,0,-1,0};
void bordare()
{
	for(int i=0;i<=n+1;i++)
		ver[i][0]=ver[i][m+1]=true;
	for(int j=0;j<=m+1;j++)
		ver[0][j]=ver[n+1][j]=true;
}
int camera(int x,int y)
{
	return (x-1)*m+y;
}

void citire()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&nec[i][j]);
	u++;
	cx[u]=(k-1)/m+1;
	cy[u]=k-(cx[u]-1)*m;
	ver[cx[u]][cy[u]]=true;
	rez=1;
	f[camera(cx[u],cy[u])]=true;
	bordare();
}
void bfs()
{
	bool ok=true;
	int ant=0;
	int act,x,y;
	x=y=0;
	while(ok)
	{
		act=u;
		ok=false;
		for(int i=ant+1;i<=act;i++)
			for(int j=0;j<4;j++)
			{
				x=cx[i]+dl[j];
				y=cy[i]+dc[j];
				if(!ver[x][y] && f[nec[x][y]])
				{
					u++;
					cx[u]=x;
					cy[u]=y;
					f[camera(cx[u],cy[u])]=true;
					ver[cx[u]][cy[u]]=true;
					rez++;
					ok=true;
				}
			}
		if(!ok)
		{
			for(int i=1;i<=u;i++)
				for(int j=0;j<4;j++)
				{
					x=cx[i]+dl[j];
					y=cy[i]+dc[j];
					if(!ver[x][y] && f[nec[x][y]])
					{
						u++;
						cx[u]=x;
						cy[u]=y;
						f[camera(cx[u],cy[u])]=true;
						ver[cx[u]][cy[u]]=true;
						rez++;
						ok=true;
					}
				}
		}
		ant=act;
	}
}
int main()
{
	freopen("castel.in","r",stdin);
	freopen("castel.out","w",stdout);
	citire();
	bfs();
	printf("%d",rez);
	return 0;
}