Cod sursa(job #141338)

Utilizator Mishu91Andrei Misarca Mishu91 Data 23 februarie 2008 00:04:12
Problema Castel Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.76 kb
#include<stdio.h>
#define Nmax 150

FILE *fin=freopen("castel.in","r",stdin),
     *fout=freopen("castel.out","w",stdout);

int a[Nmax][Nmax],n,m,k;
  

const int dx[]={-1,1,0,0},
          dy[]={0,0,1,-1};
  
int transi(int a)
{
  return a/m+1;
}

int transj(int a)
{
  return (a%m==0)?a%m+3:a%m;
}

int transij(int i, int j)
{
  return (i-1)*m+j;
}
     
int chei[Nmax][Nmax],nrs;
char viz[Nmax][Nmax],ch[Nmax*Nmax];
     
void citire()
{
  scanf("%d %d %d",&n,&m,&k);
  for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
      scanf("%d",&a[i][j]);
      int w=transij(i,j);
      chei[a[i][j]][++chei[a[i][j]][0]]=w;
    }
      
} 
     
void solve()
{
  int xc,yc,xvec,yvec,li,lf,x[Nmax*Nmax],y[Nmax*Nmax];
  li=lf=0;
  ch[k]=1;
  x[0]=transi(k);
  y[0]=transj(k);
  viz[x[0]][y[0]]=2;
  
  while(li<=lf)
  {
    xc=x[li];
    yc=y[li];
    
    for(int i=0;i<4;i++)
    {
      xvec=xc+dx[i];
      yvec=yc+dy[i];
      
      if(xvec>0 && yvec>0 && xvec<=n && yvec<=n)
      {
        if(viz[xvec][yvec]==0) viz[xvec][yvec]=1;
        
        if(viz[xvec][yvec]!=2 && ch[a[xvec][yvec]]==1)
        {
          viz[xvec][yvec]=2;
          lf++;
          nrs++;
          x[lf]=xvec;
          y[lf]=yvec;
          int t=transij(xvec,yvec);
          ch[t]=1;
          for(int i=1;i<=chei[t][0];i++)
          {
            int x1=transi(chei[t][i]),x2=transj(chei[t][i]);
            if(viz[x1][x2]==1)
            {
              lf++;
              nrs++;
              x[lf]=x1;
              y[lf]=x2;
              viz[x1][x2]=2;
            }
          }
        }
      } 
    }
    li++;
  }
  
  printf("%d",nrs+1);
} 
    
int main()
{
  citire();
  solve();
  return 0;
}