Cod sursa(job #598493)

Utilizator ELHoriaHoria Cretescu ELHoria Data 26 iunie 2011 01:22:48
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <cstdio>
#include <queue>
#include <vector>
#include <functional>
#define pereche pair<int,int>
#define st first
#define nd second
#define MP make_pair

using namespace std;

const int dx[]={0,1,0,-1},dy[]={-1,0,1,0} , NMAX = 152;
bool c[22501], A[NMAX][NMAX];
struct oha{ int cam , z ;  } D[NMAX][NMAX];
int  n , m , k , cc , key;
queue<pereche> Q;
vector<pereche> v;

int lee()
{int chei = 0;
	for(int i=0;i<(int)v.size();++i)
			Q.push(v[i]);
	pereche now , curr;
	while(!Q.empty())
	{
		now = Q.front() , Q.pop();
		for(int k=0;k<4;++k)
		{
			curr=MP(now.st+dx[k],now.nd+dy[k]);
			if(curr.st>=0 && curr.st<n && curr.nd>=0 && curr.nd<m)
				{
				if(c[D[curr.st][curr.nd].z] && !A[curr.st][curr.nd])
					{
						A[curr.st][curr.nd] = true ;
					if(!c[D[curr.st][curr.nd].cam]) 
						c[D[curr.st][curr.nd].cam] = true , v.push_back(curr),++chei , Q.push(curr);
						else
						 Q.push(curr);
				}
			}	
		}
	}
	memset(A,0,sizeof(A));
	return chei;
}

void read()
{
	freopen("castel.in","r",stdin);
	scanf("%d %d %d",&n,&m,&k);
	
	for(int i=0,cc=1;i<n;++i)
		for(int j=0;j<m;++j,++cc)
		{
			scanf("%d",&D[i][j].z) , D[i][j].cam=cc;
			if(cc==k) v.push_back(MP(i,j)) , c[k] = true;
		}

}

void solve()
{
	int t=lee();
	if(t) key+=t , solve();
}

void write()
{
	freopen("castel.out","w",stdout);
	/*
		for(int i=0;i<n;++i)
		{
			for(int j=0;j<m;++j)
				printf("%d ",D[i][j].cam);
					printf("\n");
			}
			*/
	printf("%d" , key + 1 );
}

int main()
{
	read();
	solve();
	write();

}