Cod sursa(job #81973)

Utilizator coderninuHasna Robert coderninu Data 5 septembrie 2007 15:55:58
Problema Castel Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.85 kb
#include <stdio.h>
#define infile "castel.in"
#define outfile "castel.out"
#define nmax 151

struct nod1
    {
     int xx,yy;
     struct nod1 * urm;
    };
typedef nod1 * list1;

struct nod2
    {
     int inf;
     struct nod2 * urm;
    };
typedef nod2 * list2;

int v[nmax][nmax], n, m, j, k, l, dx[4]={-1,0,1,0}, dy[4]={0,1,0,-1};
short chei[nmax*nmax], c[nmax][nmax], done;
long u=1, i, p, rez;
list1 pend[nmax*nmax];
list2 Last;

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

int inside(int,int);
int new_k(int,int);
void lee(int,int);

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

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

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

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;
}

void solve()
{
 int x, y, ch;
 list2 cheie_noua=new nod2;
 x=k/m;
 y=k%m;
 if (!y) y=m;
 else x++;
 lee(x,y);
 c[x][y]=1;
 chei[k]=1;
 cheie_noua->inf=k;
 cheie_noua->urm=NULL;
 Last=cheie_noua;
 while (cheie_noua)
     {
      ch=cheie_noua->inf;
      while (pend[ch])
	  {
	   list2 q=new nod2;
	   q->inf=new_k(pend[ch]->xx,pend[ch]->yy);
	   q->urm=NULL;
	   chei[q->inf]=1;
	   c[pend[ch]->xx][pend[ch]->yy]=1;
	   Last->urm=q;
	   Last=Last->urm;
	   lee(pend[ch]->xx,pend[ch]->yy);
	   list1 p;
	   p=pend[ch];
	   pend[ch]=pend[ch]->urm;
	   delete p;
	  }
      if (!cheie_noua->urm)
	  {
	   delete cheie_noua;
	   break;
	  }
      list2 qq;
      qq=cheie_noua;
      cheie_noua=cheie_noua->urm;
      delete qq;
     }
 for (i=1; i<=n; i++)
     for (j=1; j<=m; j++)
         rez+=c[i][j];
}

void lee(int x, int y)
{
 list1 p=new nod1, last;
 p->xx=x;
 p->yy=y;
 p->urm=NULL;
 last=p;
 while(p)
     {
      x=p->xx;
      y=p->yy;
      for (l=0; l<4; l++)
	  if (inside(x+dx[l],y+dy[l]) && !c[x+dx[l]][y+dy[l]])
	      {
	       if (chei[v[x+dx[l]][y+dy[l]]])
		   {
		    c[x+dx[l]][y+dy[l]]=1;
		    chei[new_k(x+dx[l],y+dy[l])]=1;
		    list2 ty=new nod2;
		    ty->inf=new_k(x+dx[l],y+dy[l]);
		    ty->urm=NULL;
		    Last->urm=ty;
		    Last=Last->urm;
		    list1 nou=new nod1;
		    nou->xx=x+dx[l];
		    nou->yy=y+dy[l];
		    nou->urm=NULL;
		    last->urm=nou;
		    last=last->urm;
		   }
	       else
		   {
		    int temp=v[x+dx[l]][y+dy[l]];
		    list1 op=new nod1;
		    op->xx=x+dx[l];
		    op->yy=y+dy[l];
		    op->urm=pend[temp];
		    pend[temp]=op;
		   }
	      }
      if (!(p->urm))
	  {
	   delete p;
	   break;
	  }
      list1 qqq=p;
      p=p->urm;
      delete qqq;
     }
}