Cod sursa(job #1771109)

Utilizator denniscrevusDennis Curti denniscrevus Data 5 octombrie 2016 11:04:07
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.6 kb
#include <cstdio>
#include <vector>
#define NMAX 155
using namespace std;

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

int inc,sf,k,i,j,cnt,ok, ans,l,n,m, v[NMAX][NMAX],camera, b[NMAX][NMAX];

bool chei[NMAX*NMAX];

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

vector < elem > lst[NMAX*NMAX];

inline bool bun(int x,int y)
{
    if(b[x][y])
        return 0;
    int i,x1,y1;

    for(i=0;i<4;++i)
    {
        x1=x+dx[i];
        y1=y+dy[i];
        if(b[x1][y1]==1)
            return 1;
    }
    return 0;
}

void margini()
{
    i=0;

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

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

    i=n+1;

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

    i=m+1;

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

void rezolvare()
{
    int i;
    inc=1;
    sf=1;

    qu[inc].x = (k-1) / m + 1;
    qu[inc].y = (k-1) % m + 1;
    b[qu[inc].x][qu[inc].y]=1;

    while(inc<=sf)
        {
            elem1 = qu[inc++];
            camera = (elem1.x-1)*m + elem1.y;

            if(!chei[camera])
            {
                chei[camera] = 1;
                for(i=0; i<lst[camera].size(); i++)
                {
                    v[lst[camera][i].x][lst[camera][i].y]=0;
                    if(bun(lst[camera][i].x,lst[camera][i].y))
                    {
                        aux = lst[camera][i];
                        qu[++sf] = aux;
                        b[aux.x][aux.y]=1;

                    }
                }
            }

            for(int k1=0;k1<4;k1++)
            {
                elem2.x = elem1.x + dx[k1];
                elem2.y = elem1.y + dy[k1];

                //printf("%d %d %d\n", elem2.x, elem2.y, chei[v[elem2.y][elem2.y]]);

                if(!b[elem2.x][elem2.y] && chei[v[elem2.x][elem2.y]])
                {
                    qu[++sf]=elem2;
                    b[elem2.x][elem2.y]=1;
                    //printf("%d %d\n", elem2.x, elem2.y);
                }
            }
        }
}

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

    int i,j;

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

    for(i=1;i<=n;++i)
    {
        for(j=1;j<=m;++j)
        {
            scanf("%d",&v[i][j]);
            aux.x=i;aux.y=j;
            lst[v[i][j]].push_back(aux);
        }
    }

    margini();
    chei[0]=1;
    rezolvare();

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




    printf("%d", ans);


}