Cod sursa(job #301092)

Utilizator DraStiKDragos Oprica DraStiK Data 7 aprilie 2009 22:07:54
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <stdio.h>
#define DIM 155
struct nod {int cam; 
            nod *urm;} *lst[DIM*DIM];
char viz[DIM*DIM];
int a[DIM*DIM],c[DIM*DIM];
int in=1,sf=1,n,m,k;
void read ()
{
    int i,j,nr;
    scanf ("%d%d%d",&n,&m,&k);
    for (i=1; i<=n; ++i)
        for (j=1; j<=m; ++j)
        {
            scanf ("%d",&nr);
            a[(i-1)*m+j]=nr;
        }
}
void insert (int x,int y)
{
    nod *t;
    t=new nod;
    t->urm=lst[x];
    t->cam=y;
    lst[x]=t;
}
void baga (int y)
{
    if (!viz[y])
        if (viz[a[y]])
        {
            viz[y]=1;
            c[++sf]=y;
        }
        else
            insert (a[y],y);
}
void solve ()
{
    nod *t;
    int nr,i;
    c[in]=k;
    viz[k]=1;
    while (in<=sf)
    {
        nr=c[in++];
        for (t=lst[nr]; t; t=t->urm)
            if (!viz[t->cam])
            {
                viz[t->cam]=1;
                c[++sf]=t->cam;
            }
        if (nr%m==1)
            baga (nr+1);
        else if (nr%m==0)
            baga (nr-1);
        else
        {
            baga (nr+1);
            baga (nr-1);
        }
        if (nr>=1 && nr<=m)
            baga (nr+m);
        else if (nr>=(n-1)*m+1)
            baga (nr-m);
        else
        {
            baga (nr+m);
            baga (nr-m);
        }
    }
    printf ("%d",sf);
}
int main ()
{
    freopen ("castel.in","r",stdin);
    freopen ("castel.out","w",stdout);
    read ();
    solve ();
    return 0;
}