Cod sursa(job #177439)

Utilizator omu_salcamtache tudor omu_salcam Data 12 aprilie 2008 22:39:57
Problema Castel Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include<stdio.h>
#include<search.h>
long li,ci,a,b,nc,i,j,n,m,np,p,x;
FILE *f1,*f2;
int poz[1111],chei[1111],ma[111][111],v[1111];
void insc(int a){
b=1;
for(i=1;i<=nc&&b;i++){
	if(chei[i]>=a){
		b=0;
	}
}
if(chei[i]<a&&chei[i-1]<a){
	i++;
}
if(!nc){
	i=2;
}
i--;
if(chei[i]!=a){
	nc++;
	for(j=nc+1;j>i;chei[j]=chei[j-1],j--);
	chei[i]=a;
}
}

void insp(int a){
b=1;
for(i=1;i<=np&&b;i++){
	if(poz[i]>=a){
		b=0;
	}
}
if(poz[i]<a&&poz[i-1]<a){
	i++;
}
if(!np){
  i=2;
}
i--;
if(poz[i]!=a){
  np++;
  for(j=np+1;j>i;poz[j]=poz[j-1],j--);
  poz[i]=a;
}
}

int cautare(int z){
for(j=1;j<=nc;j++){
  if(z==chei[j]){
    return 1;
  }
  if(z<chei[j]){
    return 0;
  }
}
return 0;
}

void stergere(int z){
  for(j=z;j<np;poz[j]=poz[j+1],j++);
  np--;
}

void rec(int p,int f,int t){
	if(t!=1){
		stergere(f);
	}
  insc(p);
  li=(p-1)/n+1;
  ci=(p-1)%n+1;

  if(li<m&&ma[li+1][ci]>0){
    insp(p+n);
  }
  if(li>1&&ma[li-1][ci]>0){
    insp(p-n);
  }
  if(ci<n&&ma[li][ci+1]>0){
    insp(p+1);
  }
  if(ci>1&&ma[li][ci-1]>0){
    insp(p-1);
  }
  for(v[t]=1;v[t]<=np;v[t]++){
    li=(poz[v[t]]-1)/n+1;
    ci=(poz[v[t]]-1)%n+1;
    if(cautare(ma[li][ci])){
	 ma[li][ci]*=-1;
	 insp(poz[v[t]]);
	 insc(poz[v[t]]);
	 rec(poz[v[t]],v[t],t+1);
	 v[t]--;
    }
  }
}
int main(){
f1=fopen("castel.in","r");
f2=fopen("castel.out","w");
fscanf(f1,"%ld%ld%ld",&m,&n,&a);
for(i=1;i<=m;i++){
  for(j=1;j<=n;fscanf(f1,"%d",&ma[i][j]),j++);
}
p=a;
insp(a);
rec(a,1,1);
a=0;
for(i=1;i<=m;i++){
  for(j=1;j<=n;j++){
    if(ma[i][j]<0){
	 a++;
    }
  }
}
fprintf(f2,"%ld",a);
return 0;
}