Cod sursa(job #81805)

Utilizator coderninuHasna Robert coderninu Data 4 septembrie 2007 17:34:44
Problema Castel Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <stdio.h>
#define infile "castel.in"
#define outfile "castel.out"
#define nmax 50

struct cell { int inf; short chei[nmax*nmax]; };

struct nod
    {
     int cx, cy;
     struct nod * urm;
    };

typedef nod * list;
    


int n, m, k, i, j;
short c[nmax][nmax], dx[4]={-1,0,1,0}, dy[4]={0,1,0,-1};
cell v[nmax][nmax];
list que=new nod;
long rez;

void readdata();
void writedata();
void solve();

int inside(int,int);
int new_k(int, int);
int dif(int,int,int);
void egalize(int,int,int);

int main()
{
 readdata();
 solve();
 writedata();
 return 0;
}

void readdata()
{
 freopen(infile, "r", stdin);
 scanf("%d %d %d", &n, &m, &k);
 for (i=1; i<=n; i++)
     for (j=1; j<=m; j++)
	 scanf("%d ", &v[i][j].inf);
 fclose(stdin);
}

void solve()
{
 int x, y;
 que->cx=k/m;
 que->cy=k%m;
 if (que->cy==0) que->cy=m;
 else que->cx++;
 c[que->cx][que->cy]=1;
 v[que->cx][que->cy].chei[k]=1;
 list last=que;
 while (que)
     {
      x=que->cx;
      y=que->cy;    
      for (int l=0; l<4; l++)
	  if (inside(x+dx[l],y+dy[l]) && v[x][y].chei[v[x+dx[l]][y+dy[l]].inf] && dif(x,y,l))
	      {
	       list q=new nod;
	       q->cx=x+dx[l];
	       q->cy=y+dy[l];
	       last->urm=q;
	       last=q;
	       c[last->cx][last->cy]=1;
	       egalize(x,y,l);
               v[x+dx[l]][y+dy[l]].chei[new_k(x+dx[l],y+dy[l])]=1;
	      }
      list q=que;
      que=que->urm;
      delete q;
     }
 for (i=1; i<=n; i++)
     for (j=1; j<=m; j++)
         rez+=c[i][j];
}

int inside(int x, int y)
{
 if (x<1 || x>n) return 0;
 if (y<1 || y>m) return 0;
 return 1;
}

int new_k(int x, int y)
{
 return (x-1)*m+y;
}

int dif(int x, int y, int l)
{
 int nx=x+dx[l], ny=y+dy[l];
 for (int ii=1; ii<=m*n; ii++)
     if (v[x][y].chei[ii] && !v[nx][ny].chei[ii])
	 return 1;
 return 0;
}

void egalize(int x, int y, int l)
{
 int nx=x+dx[l], ny=y+dy[l];
 for (int ii=1; ii<=n*m; ii++)
     if (v[x][y].chei[ii])
	 v[nx][ny].chei[ii]=1;
}

void writedata()
{
 freopen(outfile, "w", stdout);
 printf("%ld\n", rez);
 fclose(stdout);
}