Cod sursa(job #980156)

Utilizator manciu_ionIon Manciu manciu_ion Data 4 august 2013 09:21:36
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.5 kb

#include <iostream>
#include <cstdio>
#include <ctime>

#define NMax 150

using namespace std;

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

struct Nod{ int l, c;};

Nod *C, *Aux, x, y;
int a[NMax+2][NMax+2];
char viz[NMax+2][NMax+2];
bool uz[NMax*NMax+1];
int n, m, k;
int IncC, SfC;
int IncAux, SfAux, SfAcum;
int Key;

void _Read();
void _Solve();
inline Nod _top();
inline void _pop();
void PrintArray();
inline void _push(Nod x);
inline void _PrintSol(void);
inline int _getKey(Nod p);
inline void _getPoz(Nod& p, int Key);

int main()
{
    //double ti, tf;
    //ti = clock();

    freopen("castel.in", "rt", stdin);
    freopen("castel.out", "wt", stdout);

    _Read();
    _Solve();
    _PrintSol();

    //tf = clock();
	//printf ("\n\ntime = %.4lf\n\n", (tf-ti)/CLK_TCK);

    fclose(stdin);
    fclose(stdout);
    return 0;
}

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

    int i, j;
    for (i = 1; i <= n; ++i)
    {
        for (j = 1; j <= m; ++j)
            scanf("%d", &a[i][j]);
    }

    /// bordarea matricii
    for (i = 0; i <= n+1; ++i)
    {
        viz[i][0] = viz[i][m+1] = 3;
    }
    for (i = 1; i <= m; ++i)
    {
        viz[0][i] = viz[n+1][i] = 3;
    }
}

void PrintArray()
{
    int i, j;
    printf("\n\n");
    for (i = 0; i <= n+1; ++i)
    {
        for (j = 0; j <= m+1; ++j)
            printf("%3d", viz[i][j]);
        printf("\n");
    }
}

void _Solve()
{
    IncC = SfC = 0;
    IncAux = SfAux = 0;
    C = new Nod[n*m];
    Aux = new Nod[n*m];
    /// marchez cheia k
    _getPoz(x,k);
    uz[k] = true;
    uz[a[x.l][x.c]] = true;
    viz[x.l][x.c] = 1;
    _push(x);
    bool ok;
    do {
        ok = false;
        while (IncC < SfC)
        {
            x = _top(); _pop();
            //printf("%d %d %d\n", x.l, x.c, _getKey(x));
            for (int k = 0; k < 4; ++k)
            {
                y.l = x.l+dx[k];
                y.c = x.c+dy[k];
                if (viz[y.l][y.c] == 0 || viz[y.l][y.c] == 2)
                {
                    int key = _getKey(y);
                    //printf("%d %d %d\n", y.l, y.c, _getKey(y));
                    if (uz[a[y.l][y.c]] or uz[key])
                    {
                        //printf("%d %d %d\n", y.l, y.c, _getKey(y));
                        uz[key] = true;
                        uz[a[y.l][y.c]] = true;
                        viz[y.l][y.c] = 1;
                        _push(y);
                    }
                    else { viz[y.l][y.c] = 2; Aux[SfAux++] = y; }
                 }
            }
        }

        for (IncAux = SfAcum = 0; IncAux < SfAux; ++IncAux)
        {
            y = Aux[IncAux];
            if (viz[y.l][y.c] != 1)
                if (uz[_getKey(y)] or uz[a[y.l][y.c]])
                {
                    uz[_getKey(y)] = 1;
                    uz[a[y.l][y.c]] = 1;
                    viz[y.l][y.c] = 1;
                    _push(y);
                    ok = true;
                }
                else { Aux[SfAcum++] = y; }
        }

        SfAux = SfAcum;
    } while (ok);

}

inline void _PrintSol(void)
{
    printf("%d\n", SfC);
}

inline void _push(Nod x)
{
    C[SfC++] = x;
}

inline Nod _top()
{
    return C[IncC];
}

inline void _pop()
{
    IncC++;
}

inline void _getPoz(Nod& p, int Key)
{
    p.l = (Key-1)/m+1;
    p.c = (Key-1)%m+1;
}

inline int _getKey(Nod p)
{
    return (m*(p.l-1)+p.c);
}