Cod sursa(job #863525)

Utilizator Kira96Denis Mita Kira96 Data 23 ianuarie 2013 21:32:12
Problema Castel Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 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,xi,yi,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);
	key[k]=1;
	while(k>M)
	{
		xi++;
		k-=M;
	}
	++xi;
	qx[1]=xi;
	yi=k;
	qy[1]=yi;
	for(i=1;i<=n;++i)
		for(j=1;j<=M;++j)
			scanf("%d",&m[i][j]);
	sol=1;
	mat[xi][yi]=1;
	nr=1;
	sol1=-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(!key[m[xc][yc]]&&xc>0&&yc>0&&xc<=n&&yc<=M&&!check[x[p]][y[p]])
					{
						check[x[p]][y[p]]=1;
						qx[++nr]=x[p];
						qy[nr]=y[p];
					}
					else
					if(xc>0&&yc>0&&xc<=n&&yc<=M&&key[m[xc][yc]]&&!mat[xc][yc])
					{
						++sol;
						mat[xc][yc]=1;
						key[(xc-1)*M+yc]=1;
						x[++u]=xc;
						y[u]=yc;
					}
				}
				++p;
			}
		}
	}
	printf("%d",sol);
	return 0;
}