Cod sursa(job #863577)

Utilizator Kira96Denis Mita Kira96 Data 23 ianuarie 2013 22:07:20
Problema Castel Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<stdio.h>
#define N 151
#define Q 30000
using namespace std;
int dx[]={0,0,-1,0,1};
int dy[]={0,-1,0,1,0};
int m[N][N],i,j,n,k,u,p,nr,xc,yc,key[Q],qx[Q],qy[Q],x[Q],y[Q],sol,sol1,M; 
bool mat[N][N],check[N][N];
int main ()
{
	freopen ("castel.in","r",stdin);
	freopen ("castel.out","w",stdout);
	scanf("%d%d%d",&n,&M,&k);
	qx[1]=k/M+1;
	qy[1]=k%M;
	for(i=1;i<=n;++i)
		for(j=1;j<=M;++j)
			scanf("%d",&m[i][j]);
	mat[qy[1]][qx[1]]=1;
	nr=sol1=key[k]=1;
	while(sol!=sol1)
	{
		sol1=sol;
		for(k=1;k<=nr;++k)
		{
			x[1]=qx[k];
			y[1]=qy[k];
			p=u=1;
			while(p<=u)
			{
				for(i=1;i<=4;++i)
				{
					xc=x[p]+dx[i];
					yc=y[p]+dy[i];
					if(xc<1||yc<1||xc>n||yc>M||mat[xc][yc])
						continue;
					if(key[m[xc][yc]])
					{
						++sol;
						mat[xc][yc]=1;
						key[(xc-1)*M+yc]=1;
						x[++u]=xc;
						y[u]=yc;
					}
					else
					if(!check[x[p]][y[p]])
					{
						check[x[p]][y[p]]=1;
						qx[++nr]=x[p];
						qy[nr]=y[p];
					}
				}
				++p;
			}
		}
	}
	printf("%d",sol);
	return 0;
}