Cod sursa(job #582220)

Utilizator RengelBotocan Bogdan Rengel Data 15 aprilie 2011 02:11:47
Problema Castel Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include<cstdio>

int a[160][160];
int b[160][160];
int c[160][160];
int key[25000];
int cd_u[25000];
int cd_d[25000];
int xx[25000],kx;
int yy[25000];
int n,m,p,i,sw,s2w,max=1;
int first=1,last=1;

void read(){
	
	int c;
	scanf("%d%d%d",&n,&m,&c);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			scanf("%d",&a[i][j]);
			b[i][j]=(i-1)*m+j;
			if(b[i][j]==c){
				cd_u[1]=i;
				cd_d[1]=j;
			}
		}
	
	
}

int state(int x,int y){
	
	if(x<1) return 0;
	if(y<1) return 0;
	if(x>n) return 0;
	if(y>m) return 0;
	if(c[x][y]) return 0;
	return 1;
	
}

void coada(int x,int y){
	
	if(c[x][y]==0) max++;
	c[x][y]=1;
	cd_u[++last]=x;
	cd_d[last]=y;
	sw=0;
	
}

void fill(int x,int y){
	
	if(state(x+1,y))
		if(key[a[x+1][y]]){
			coada(x+1,y);
			key[b[x+1][y]]=1;
			s2w++;
		}
		else{
			xx[++kx]=x;
			yy[kx]=y;
		}
	if(state(x-1,y))
		if(key[a[x-1][y]]){
			coada(x-1,y);
			key[b[x-1][y]]=1;
			s2w++;
		}
		else{
			xx[++kx]=x;
			yy[kx]=y;
		}
	if(state(x,y+1))
		if(key[a[x][y+1]]){
			coada(x,y+1);
			key[b[x][y+1]]=1;
			s2w++;
		}
		else{
			xx[++kx]=x;
			yy[kx]=y;
		}
	if(state(x,y-1))
		if(key[a[x][y-1]]){
			coada(x,y-1);
			key[b[x][y-1]]=1;
			s2w++;
		}
		else{
			xx[++kx]=x;
			yy[kx]=y;
		}
	
}

int main(){
	
	freopen("castel.in","r",stdin);
	freopen("castel.out","w",stdout);
	
	read();
	
	c[cd_u[1]][cd_d[1]]=1;
	key[b[cd_u[1]][cd_d[1]]]=1;
	
	while(!sw){
		
		sw=1;
		p=last;
		for(i=first;i<=p;i++)
			fill(cd_u[i],cd_d[i]);
		first=p+1;
		
	}
	
	s2w=1;
	while(s2w){
		
		s2w=0;
		for(i=1;i<=kx;i++)
			coada(xx[i],yy[i]);
		
		kx=0;
		
		sw=1;
		p=last;
		for(i=first;i<=p;i++)
			fill(cd_u[i],cd_d[i]);
		first=p+1;
		
	}
	
	printf("%d",max);
	
	return 0;
	
}