Cod sursa(job #260218)

Utilizator petroMilut Petronela petro Data 16 februarie 2009 20:19:13
Problema Castel Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.87 kb
#include<stdio.h>

FILE *f=fopen("castel.in","r");
FILE *g=fopen("castel.out","w");

int m,n,k,X,Y;

#define M 151

int a[M][M], b[M][M], v[M*M];

void citire()
{int i,j,l=0;

 fscanf(f,"%d%d%d",&m,&n,&k);

 for(i=1;i<=m;i++)
  for(j=1;j<=n;j++)
   {fscanf(f,"%d",&a[i][j]);
    b[i][j]=++l;
    if(l==k) {X=i;Y=j;}
    }

 fclose(f);
 }

int verif(int l,int x, int y)
{int i;

 for(i=1;i<=l;i++)
  if(v[i]==a[x][y]) return 0;

return 1;                                    
}

int lee(int x, int y,int &l)
{int p,u,j,i,cx[M*M], cy[M*M];

 p=u=1;
 cx[p]=x;
 cy[p]=y;

 while(p<=u)
 {x=cx[p];
  y=cy[p];

  if(x-1>=1) if(verif(l,x-1,y)==0) {v[++l]=b[x-1][y];
				    u++;
				    cx[u]=x-1;
				    cy[u]=y;
				    a[x-1][y]=b[x-1][y]=0;}

  if(x+1<=m) if(verif(l,x+1,y)==0) {v[++l]=b[x+1][y];
				    u++;
				    cx[u]=x+1;
				    cy[u]=y;
				    a[x+1][y]=b[x+1][y]=0;}

  if(y-1>=1) if(verif(l,x,y-1)==0) {v[++l]=b[x][y-1];
				    u++;
				    cx[u]=x;
				    cy[u]=y-1;
				    a[x][y-1]=b[x][y-1]=0;}

  if(y+1<=n) if(verif(l,x,y+1)==0) {v[++l]=b[x][y+1];
				    u++;
				    cx[u]=x;
				    cy[u]=y+1;
				    a[x][y+1]=b[x][y+1]=0;}

  p++;}

 /*for(i=1;i<=m;i++)
 {for(j=1;j<=n;j++)
   fprintf(g,"%d ",b[i][j]);
  fprintf(g,"\n");}
			 */
return u;}

int verif2(int cx[M*M], int cy[M*M],int p, int u, int x, int y)
{int i;

 for(i=1;i<=u;i++)
  if(x==cx[i] && y==cy[i]) return 0;

return 1;}


int lee2(int x, int y, int &l)
{int p,u,cx[M*M],cy[M*M];

 p=u=1;

 cx[u]=x;
 cy[u]=y;
                                              
 while(p<=u)
 {x=cx[p];
  y=cy[p];

  if(x-1>=1) {if(a[x-1][y]==0&&verif2(cx,cy,p,u,x-1,y)) {u++;
				cx[u]=x-1;
				cy[u]=y;}
	      else if(verif(l,x-1,y)==0) {v[++l]=b[x-1][y];
						    u++;
						    cx[u]=x-1;
						    cy[u]=y;
						    a[x-1][y]=b[x-1][y]=0;}
	      }

  if(x+1<=m) {if(a[x+1][y]==0 && verif2(cx,cy,p,u,x+1,y)) {u++;
				cx[u]=x+1;
				cy[u]=y;}
	     else if(verif(l,x+1,y)==0) {v[++l]=b[x+1][y];
				    u++;
				    cx[u]=x+1;
				    cy[u]=y;
				    a[x+1][y]=b[x+1][y]=0;}
	     }

  if(y-1>=1) {if(a[x][y-1]==0&& verif2(cx,cy,p,u,x,y-1)) {u++;
				cx[u]=x;
				cy[u]=y-1;}
	     else if(verif(l,x,y-1)==0) {v[++l]=b[x][y-1];
				    u++;
				    cx[u]=x;
				    cy[u]=y-1;
				    a[x][y-1]=b[x][y-1]=0;}
	     }

  if(y+1<=n) {if(a[x][y+1]==0&& verif2(cx,cy,p,u,x,y+1)) {u++;
				cx[u]=x;
				cy[u]=y+1;}
	      else if(verif(l,x,y+1)==0) {v[++l]=b[x][y+1];
				    u++;
				    cx[u]=x;
				    cy[u]=y+1;
				    a[x][y+1]=b[x][y+1]=0;}
	      }

  p++;}

return u;}


int main()
{int x,y,l,u,U;

 citire();

 l=1;
 v[l]=b[X][Y];
 b[X][Y]=a[X][Y]=0;

 x=X;
 y=Y;

u=lee(x,y,l);

U=lee2(x,y,l);

 while(u!=U)
 {u=U;
   U=lee2(x,y,l);}

 fprintf(g,"%d\n",l);


 fclose(g);

 return 0;
 }