Cod sursa(job #1770857)

Utilizator denniscrevusDennis Curti denniscrevus Data 4 octombrie 2016 22:17:13
Problema Castel Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.61 kb
#include <cstdio>
#define NMAX 155
#define DIM 10000
using namespace std;

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

char buff[DIM];
int poz;

void citeste(int &numar)
{
     numar = 0;
     while (buff[poz] < '0' || buff[poz] > '9')
     {
          if (++poz == DIM)
               fread(buff,1,DIM,stdin),poz=0;
     }
     while ('0'<=buff[poz] && buff[poz]<='9')
     {
          numar = numar*10 + buff[poz] - '0';
          if (++poz == DIM)
               fread(buff,1,DIM,stdin),poz=0;
     }

}

int inc,sf,k,i,j,cnt,ok, ans,l,n,m, v[NMAX][NMAX];
bool b[NMAX][NMAX], chei[NMAX*NMAX], bagat[NMAX][NMAX];

struct elem
{
    short x;
    short y;
}qu[NMAX*NMAX], lst[NMAX*NMAX], elem1,elem2, aux;

void margini()
{
    i=0;

    for(j=0;j<=m+1;j++)
        b[i][j]=1;

    for(j=1;j<=n+1;j++)
        b[j][i]=1;

    i=n+1;

    for(j=1;j<=m+1;j++)
        b[i][j]=1;

    i=m+1;

    for(j=1;j<=n+1;j++)
        b[j][i]=1;
}

void rezolvare()
{
    cnt=0;
    inc=1;
    sf=1;
    chei[k]=1;
    qu[inc].x = (k-1) / n + 1;
    qu[inc].y = (k-1) % m + 1;
    ok=0;
    while(!ok)
    {
        ok=1;
        while(inc<=sf)
        {
            ok=0;
            elem1 = qu[inc++];
            for(k=0;k<4;k++)
            {
                elem2.x = elem1.x + dx[k];
                elem2.y = elem1.y + dy[k];

                if(!b[elem2.x][elem2.y] && chei[v[elem2.x][elem2.y]])
                {
                    qu[++sf]=elem2;
                    b[elem2.x][elem2.y]=1;
                    //g<<elem2.x<<" "<<elem2.y<<" "<<m*(elem2.x-1) + elem2.y<<"\n";
                    chei[m*(elem2.x-1) + elem2.y]=1;
                }
                else if(!b[elem2.x][elem2.y] && !bagat[elem2.x][elem2.y])
                {
                    lst[++cnt] = elem2;
                    bagat[elem2.x][elem2.y]=1;
                }
            }
        }
        for(i=1;i<=cnt;i++)
        {
            if(!b[lst[i].x][lst[i].y] && chei[v[lst[i].x][lst[i].y]])
            {
                qu[++sf] = lst[i];
                chei[m*(lst[i].x-1) + lst[i].y] = 1;
                b[lst[i].x][lst[i].y]=1;
                ok=0;
            }
        }
        }
    }

int main()
{
    freopen("castel.in","r", stdin);
    freopen("castel.out", "w", stdout);

    scanf("%d%d%d", &n,&m,&k);

    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            citeste(v[i][j]);

    margini();
    rezolvare();

    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(b[i][j])
                ans++;

    printf("%d", ans);


}