Cod sursa(job #56377)

Utilizator raula_sanChis Raoul raula_san Data 29 aprilie 2007 14:42:57
Problema Castel Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.1 kb
#include <cstdio>

#define dim 151

struct nod
{   int x, y;
    nod *next;
} *l, *e, *le, *ee;

int A[dim][dim], C[dim][dim];
int key[dim*dim];
int N, M, K;

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

void get_data();
void coord(int&, int&, int);
void number(int&, int, int);
void lee();
void print();

int main()
{
    get_data();
	lee();
    print();

    return 0;
}

void get_data()
{
    freopen("castel.in", "r", stdin);

    int i, j;
    for(scanf("%d %d %d", &N, &M, &K), i=1; i<=N; ++i)
        for(j=1; j<=M; ++j)
            scanf("%d", &A[i][j]);

    fclose(stdin);
}

void coord(int &x, int &y, int k)
{
    if( !(k % M) )
    {
        x = k / M;
        y = M;
    }
    else
    {
        x = (k / M) + 1;
        y = k % M;
    }
}

void number(int &k, int x, int y)
{
    k = (x-1) * M;
    k += y;
}

void lee()
{
    int i, j, nx, ny, nc, good;

    l = new nod;
    coord(l->x, l->y, K);

	key[K] = 1;

	l->next = NULL;
    e = l;

	C[l->x][l->y] = 1;

good = 1;
while(good)
{
    good = 0;

    while(l)
	{
        for(i=0; i<4; ++i)
        {
            nx = l->x + dx[i];
            ny = l->y + dy[i];

            if(nx >= 1 && nx <= N && ny >= 1 && ny <= M)
            {
				if(key[A[nx][ny]])
                {
					if(C[nx][ny] != 1)
					{
                        number(nc, nx, ny);

                        C[nx][ny] = 1;

                        nod *p = new nod;
                        p->x = nx;
                        p->y = ny;

                        key[nc] = 1;

                        p->next = NULL;

                        e->next = p;
                        e = p;
					}
                }
                else if(!C[nx][ny])
                {
                    C[nx][ny] = 2;

                    nod *p = new nod;
                    p->x = nx;
                    p->y = ny;
                    p->next = NULL;

                    if(le == NULL)
                        le = ee = p;
                    else
                    {
                        ee->next = p;
                        ee = p;
                    }
                }
            }
        }

        nod *p = l;
		l = l->next;
        delete p;
    }

    l = e = NULL;

    nod *g = le;

    while(g)
    {
		if(key[A[g->x][g->y]] && C[g->x][g->y] == 2)
		{
			good = 1;

			C[g->x][g->y] = 1;

			number(nc, g->x, g->y);

			key[nc] = 1;

			nod *p = new nod;
			p->x = g->x;
			p->y = g->y;
			p->next = NULL;

			if(l == NULL)
				l = e = p;
			else
			{
				e->next = p;
				e = p;
			}

			p = g;
			g = g->next;
			delete p;
		}
		else if(C[g->x][g->y] == 1)
		{
            nod *p = g;
            g = g->next;
            delete p;
        }
        else
            g = g->next;
	}

	le = ee = NULL;
}
}

void print()
{
    freopen("castel.out", "w", stdout);

    int i, j, ret = 0;

    for(i=1; i<=N; ++i)
        for(j=1; j<=M; ++j)
			if(C[i][j] == 1) ++ ret;

    printf("%d", ret);

    fclose(stdout);
}