Cod sursa(job #1771044)

Utilizator denniscrevusDennis Curti denniscrevus Data 5 octombrie 2016 09:58:48
Problema Castel Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.63 kb
#include <cstdio>
#include <vector>
#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;

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

bool b[NMAX][NMAX], chei[NMAX*NMAX];

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

vector < elem > lst[NMAX*NMAX];

bool check(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]=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;
    b[qu[inc].x][qu[inc].y]=1;
    ok=0;

    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(check(lst[camera][i].x, lst[camera][i].y))
                    {
                        qu[++sf] = lst[camera][i];
                        b[lst[camera][i].x][lst[camera][i].y]=1;
                        //printf("%d %d\n", lst[camera][i].x, lst[camera][i].y);
                        //chei[(lst[camera][i].x-1)*m + lst[camera][i].y]=1;
                    }
                }
            }

            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;
                }
            }
        }
}

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++)
        {
            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);


}