Cod sursa(job #1732729)

Utilizator antanaAntonia Boca antana Data 22 iulie 2016 14:36:07
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <cstdio>
#define MAXN 150

struct aa{
    int x, y;
}val[MAXN*MAXN+1];

bool viz[MAXN+1][MAXN+1], f[MAXN*MAXN+1];
int ic, sf, lista[MAXN*MAXN+1], next[MAXN*MAXN+1], n, m, coada[MAXN*MAXN+1], r, v[MAXN+1][MAXN+1];

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

inline void adauga(int key, int lin, int col)
{
    val[++r].x=lin;
    val[r].y=col;
    next[r]=lista[key];
    lista[key]=r;
}

void dfs(int lin, int col)
{
    int linie, coloana;
    viz[lin][col]=1;
    if(!f[(lin-1)*m + col])
    {
        f[(lin-1)*m + col]=1;
            coada[++sf]=(lin-1)*m + col;
    }

    for(int i=0;i<4;++i)
    {
        linie=lin+dx[i];
        coloana=col+dy[i];
        if(linie>=1 && linie<=n && coloana>=1 && coloana<=m && !viz[linie][coloana] && f[v[linie][coloana]])
            dfs(linie, coloana);
    }
}
int main()
{
    freopen("castel.in", "r", stdin);
    freopen("castel.out", "w", stdout);
    int k, key, sl, sc, cells=0, l, c, p;
    scanf("%d%d%d", &n, &m, &k);

    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            scanf("%d", &key), adauga(key, i, j), v[i][j]=key;

    ic=sf=1;
    sl=(k+m-1)/m;
    sc=k%m;
    if(sc==0)
        sc=m;
    viz[sl][sc]=f[k]=1;

    coada[ic]=k;
    while(ic<=sf)
    {
        f[coada[ic]]=1;
        p=lista[coada[ic]];

        while(p)
        {
            l=val[p].x;
            c=val[p].y;

            int ican=0;
            if(l != sl || c != sc)
                for(int i=0;i<4;++i)
                    if(viz[l+dx[i]][c+dy[i]])
                        ican=1;
            if(ican)
                dfs(l, c);
            p=next[p];
        }
        ic++;
    }

    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            if(viz[i][j])
                cells++;

    printf("%d", cells);
    return 0;
}