Cod sursa(job #61382)

Utilizator Binary_FireFlorin Pg Binary_Fire Data 19 mai 2007 10:42:53
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <stdio.h>
#include <vector>
#define fin  "castel.in"
#define fout "castel.out"
#define Nmax 151

using namespace std;

struct nod { int x; int y; };

int map[Nmax][Nmax],vi_np[Nmax*Nmax],key[Nmax*Nmax];
int M,N,P;
nod t1[Nmax*Nmax];
vector < nod > t2[Nmax*Nmax];
int st1,dr1,ret;

void exp(int x,int y) {
int tmp;
int i;
nod aux;

	if ( x<1 || y<1 || x>M || y>N )
		return ;
	if ( map[x][y]==-1 )
		return ;
	
	tmp=(x-1)*N+y;
	
	if ( key[map[x][y]] == 1 ) {
		t1[++dr1].x=x;
		t1[dr1].y=y;
		key[tmp]=1;
		map[x][y]=-1;
	}
	
	else {
		aux.x=x; aux.y=y;
		if (!vi_np[tmp]) 
			t2[map[x][y]].push_back(aux);
		vi_np[tmp]=1;
	}
		
}

void unlock(int p) {
int i=0,x=0,y=0;
	for (i=0;i<t2[p].size();++i) {
		x=t2[p][i].x;
		y=t2[p][i].y;
		t1[++dr1].x=x;
		t1[dr1].y=y;
		map[x][y]=-1;
	}
	t2[p].clear();
}

void bf() {
int i,tmp,x,y;
	tmp=dr1;
	for (i=st1;i<=tmp;++i) {
		
		x=t1[i].x; y=t1[i].y;
		
		exp(x-1,y); exp(x+1,y);
		exp(x,y+1); exp(x,y-1);	
		
		unlock((x-1)*N+y);
	}

	st1=tmp+1;
	
	if (st1<=dr1) bf();
}

int main() {
int i,j,k=0;
	freopen(fin,"r",stdin); freopen(fout,"w",stdout);

	scanf("%d%d%d",&M,&N,&P);

	for (i=1;i<=M;++i)
	for (j=1;j<=N;++j) {
		scanf("%d",&map[i][j]);
		++k; 
		if (k==P) {
			t1[1].x=i; t1[1].y=j;
			map[i][j]=-1;
			key[P]=1; 
		}
	}
	
	st1=1; dr1=1;

	bf();
		
	for (i=1;i<=M;++i)
	for (j=1;j<=N;++j)
		if (map[i][j]==-1)
			++ret;

	printf("%d\n",ret);

	return 0;
}