Cod sursa(job #579174)

Utilizator eukristianCristian L. eukristian Data 11 aprilie 2011 21:47:47
Problema Castel Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.92 kb
#include <cstdio>
#include <queue>
using std::queue;

struct Room{
	short nr;
	Room *next;
};

char vizitat[22501];
short A[22501];
int N, M, K;

Room *lst[22501];
inline bool viz(int key)
{
    return vizitat[key] & 1;
}

inline bool added(int key)
{
    return vizitat[key] & 2;
}

int main()
{
    int count = 0;
	FILE *f = fopen("castel.in",  "r");
	FILE *g = fopen("castel.out", "w");

	fscanf(f, "%d %d %d", &N, &M, &K);

    for (int i = 1 ; i <= M * N ; ++i)
        fscanf(f, "%hd", &A[i]);

    vizitat[K] = true;
	queue<short> Q;
	Q.push(K);

	while (!Q.empty())
	{
		short x = Q.front();
		Q.pop();

		int line = (x + M - 1) / M;
		int col = x % M;
		if (col == 0) col = M;

        Room *p = lst[x];

        while (p != 0)
        {
            vizitat[p->nr] = true;
            Q.push(p->nr);
            p = p->next;
            delete lst[x];
            lst[x] = p;
        }

        if (line > 1 && !viz((line - 2) * M + col))
        {
            int key = (line - 2) * M + col;
            if (viz(A[key]))
            {
                vizitat[key] |= 1;
                Q.push(key);
            }
            else if (!added(key))
            {
                Room *t = new Room;
                t->nr = key;
                t->next = lst[A[key]];
                lst[A[key]] = t;
                vizitat[key] |= 2;
            }
        }

        if (line < N && !viz(line * M + col))
        {
            int key = line * M + col;
            if (viz(A[key]))
            {
                vizitat[key] |= 1;
                Q.push(key);
            }
            else if (!added(key))
            {
                Room *t = new Room;
                t->nr = key;
                t->next = lst[A[key]];
                lst[A[key]] = t;
                vizitat[key] |= 2;
            }
        }

        if (col > 1 && !viz((line - 1) * M + col - 1))
        {
            int key = (line - 1) * M + col - 1;
            if (viz(A[key]))
            {
                vizitat[key] |= 1;
                Q.push(key);
            }
            else if (!added(key))
            {
                Room *t = new Room;
                t->nr = key;
                t->next = lst[A[key]];
                lst[A[key]] = t;
                vizitat[key] |= 2;
            }
        }

        if (col < M && !viz((line - 1) * M + col + 1))
        {
            int key = (line - 1) * M + col + 1;
            if (viz(A[key]))
            {
                vizitat[key] |= 1;
                Q.push(key);
            }
            else if (!added(key))
            {
                Room *t = new Room;
                t->nr = key;
                t->next = lst[A[key]];
                lst[A[key]] = t;
                vizitat[key] |= 2;
            }
        }

        count++;
	}

    fprintf(g, "%d\n", count);

	return 0;
}