Cod sursa(job #1153471)

Utilizator eustatiuDima Eustatiu eustatiu Data 25 martie 2014 15:07:01
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <stdio.h>
long cx[5]={0,-1,0,1,0};
long cy[5]={0,0,1,0,-1};
using namespace std;
struct nod
{
    short x,y;
    nod *urm;
};
int n,m,i,j,p,x,y,nr;
short a[151][151],d[151][151];
bool c[23001];//chei
nod *s1[23001],*s2[23001],*tmp;
void fill (int x, int y)
{
    nod *t;
    if (c[d[x][y]]==0)
    {
        c[d[x][y]]=1;
                    t=s1[d[x][y]]->urm;
                    while (t->urm)
                    {
                        if (a[t->x][t->y]>0)
                        {
                            a[t->x][t->y]=0;
                            fill(t->x,t->y);
                        }
                        tmp=t->urm;
                        delete(t);
                        t=tmp;
                    }
    }
    for (short i=1;i<=4;i++)
    {
        if ((x+cx[i]>0&&x+cx[i]<=m)&&(y+cy[i]<=n&&y+cy[i]>0))
            if (a[x+cx[i]][y+cy[i]]>0)
                if (c[a[x+cx[i]][y+cy[i]]])
                {
                    a[x+cx[i]][y+cy[i]]=0;
                    fill(x+cx[i],y+cy[i]);
                }
                else
                {
                    s2[a[x+cx[i]][y+cy[i]]]->x=x+cx[i];
                    s2[a[x+cx[i]][y+cy[i]]]->y=y+cy[i];
                    nod *p=new(nod);
                    s2[a[x+cx[i]][y+cy[i]]]->urm=p;
                    p->urm=0;
                }
    }
}
int main()
{
    freopen ("castel.in","r",stdin);
    freopen ("castel.out","w",stdout);
    scanf ("%ld%ld%ld",&m,&n,&p);
    for (i=1;i<=m;i++)
        for (j=1;j<=n;j++)
        {
            scanf ("%ld",&a[i][j]);
            d[i][j]=(i-1)*n+j;
        }
    p--;
    x=p/n+1;
    y=p%n+1;
    j=n*m;
    for (i=1;i<=j;i++)
        {
            s1[i]=new(nod);
            s2[i]=new(nod);
            s1[i]->urm=s2[i];
            s2[i]->urm=0;
        }
    a[x][y]=0;
    p=1;
    c[p]=0;

    fill (x,y);
    nr=0;
    for (i=1;i<=m;i++)
        for (j=1;j<=n;j++)
            if (!a[i][j])
                nr++;
    printf ("%ld",nr);
    return 0;
}