Cod sursa(job #150778)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 7 martie 2008 13:29:27
Problema Castel Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include<stdio.h>
FILE*fin=fopen("castel.in","r");
FILE*fout=fopen("castel.out","w");
#define maxn 50
struct nod
{
  int inf;
  nod*urm;
};
int a[maxn][maxn],cheie[maxn*maxn],c[maxn*maxn],proc[maxn*maxn],v[maxn*maxn];
nod *acc[maxn*maxn];
int main()
{
  int col[4],lin[4],st,dr,i,j,n,m,x,y,k,dir;
  nod *q;
  col[0]=0;col[1]=1;col[2]=0;col[3]=-1;
  lin[0]=-1;lin[1]=0;lin[2]=1;lin[3]=0;
  fscanf(fin,"%d%d%d",&n,&m,&k);
  for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
    {
      fscanf(fin,"%d",&a[i][j]);
      proc[(i-1)*m+j]=0;
      cheie[(i-1)*m+j]=0;
      acc[(i-1)*m+j]=NULL;
      v[(i-1)*m+j]=0;
    }
  fclose(fin);
  proc[k]=1;
  v[k]=1;
  st=dr=1;
  c[st]=k;
  while(st<=dr)
  {
    cheie[c[st]]=1;
    if(c[st]%m==0)
    {
      i=c[st]/m;
      j=m;
    }
    else
    {
      i=c[st]/m+1;
      j=c[st]%m;
    }
    for(dir=0;dir<=3;dir++)
    {
      x=i+lin[dir];
      y=j+col[dir];
      if(1<=x&&x<=n&&1<=y&&y<=m)
      if(!proc[(x-1)*m+y])
      {
	proc[(x-1)*m+y]=1;
	if(cheie[a[x][y]])
	{
	  dr++;
	  c[dr]=(x-1)*m+y;
	  v[(x-1)*m+y]=1;
	}
	else
	{
	  q=new nod;
	  q->inf=(x-1)*m+y;
	  q->urm=acc[a[x][y]];
	  acc[a[x][y]]=q;
	}
      }
    }
    q=acc[c[st]];
    while(q)
    {
      dr++;
      c[dr]=q->inf;
      v[c[dr]]=1;
      q=q->urm;
    }
    st++;
  }
  fprintf(fout,"%d",dr);
  fclose(fout);
  return 0;
}