Cod sursa(job #82048)

Utilizator DastasIonescu Vlad Dastas Data 5 septembrie 2007 17:28:39
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <cstdio>
#include <vector>

const int maxn = 152;

FILE *in = fopen("castel.in","r"), *out = fopen("castel.out","w");

int m, n, k;
int a[maxn][maxn] = {{0}};

void read()
{
    fscanf(in, "%d %d %d", &m, &n, &k);
    --k;

    for ( int i = 0; i < m; ++i )
        for ( int j = 0; j < n; ++j )
            fscanf(in, "%d", &a[i][j]), --a[i][j];
}

struct coada
{
    short x, y;
};

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

coada b[maxn*maxn];
char chei[maxn*maxn] = {0};
char viz[maxn][maxn];
std::vector<int> h[maxn*maxn];

int lee(int x, int y)
{
    int p = 0, u = 0;
    b[p].x = x;
    b[p].y = y;
    int cnt = 1;

    chei[k] = 1;
    viz[x][y] = 1;

    int X, Y;
    while ( p <= u )
    {
        X = b[p].x;
        Y = b[p].y;

        for ( std::vector<int>::iterator it = h[n*X + Y].begin(); it != h[n*X + Y].end(); ++it )
            if ( !viz[*it/n][*it%n] )
            {
                ++cnt, viz[*it/n][*it%n] = 2, chei[*it] = 1;
                ++u;
                b[u].x = *it/n;
                b[u].y = *it%n;
            }

        for ( int i = 0; i < 4; ++i )
        {
            X = b[p].x + dx[i];
            Y = b[p].y + dy[i];

            if ( X < 0 || Y < 0 || X > m - 1 || Y > n - 1 )
                continue;

            if ( !viz[X][Y] && chei[ a[X][Y] ] == 1 )
            {
                ++u;
                b[u].x = X;
                b[u].y = Y;
                ++cnt;
                chei[n*X + Y] = 1;
                viz[X][Y] = 1;

            }
            else if ( chei[ a[X][Y] ] == 0 )
                h[ a[X][Y] ].push_back(n*X + Y);
        }

        ++p;
    }

    return cnt;
}

int main()
{
    read();


    int x = 0, y = 0;
    x = k / n;
    y = k % n;

    fprintf(out, "%d\n", lee(x, y));


	return 0;
}