Cod sursa(job #340980)

Utilizator CezarMocanCezar Mocan CezarMocan Data 17 august 2009 11:08:28
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <cstdio>
#include <vector>
#define maxn 154

using namespace std;

struct poz {
	int x, y;
};

const int dl[4] = {0, 0, 1, -1};
const int dc[4] = {1, -1, 0, 0};

int n, m, k, i, j;
bool have[maxn * maxn];
poz q[maxn * maxn];
int v[maxn][maxn];
bool viz[maxn][maxn];
bool vizk[maxn][maxn];
vector <poz> key[maxn * maxn];

void poz_to_coord(int poz, int &x, int &y) {
	x = (poz - 1) / m + 1;
	y = poz % m; 
	if (y == 0)
		y = m;
}

int coord_to_poz(int x, int y) {
	return ((x - 1) * m + y);
}

void bfs() {
	int p, u, i, l, c, lnou, cnou, d;
	int nw;

	poz_to_coord(k, l, c);

	p = u = 1;
	q[1].x = l; q[1].y = c;
	viz[l][c] = 1;

	while (p <= u) {
		l = q[p].x; c = q[p].y;
		viz[l][c] = 1;

		nw = coord_to_poz(l, c);
		have[nw] = 1;

//		fprintf(stderr, "%d  %d %d  %d\n", nw, l, c, key[nw].size());

		for (i = 0; i < key[nw].size(); i++) {
			u++;
			q[u] = key[nw][i];
		}
		key[nw].clear();

		for (d = 0; d < 4; d++) {
			lnou = l + dl[d];
			cnou = c + dc[d];
			if (lnou > 0 && lnou <= n && cnou > 0 && cnou <= m && viz[lnou][cnou] == 0) {
				if (have[v[lnou][cnou]]) {
					u++;
					q[u].x = lnou; q[u].y = cnou;
//					viz[lnou][cnou] = 1;
				}
				else  if (vizk[lnou][cnou] == 0) {
					poz aux;
					aux.x = lnou; aux.y = cnou;
					key[v[lnou][cnou]].push_back(aux);
					vizk[lnou][cnou] = 1;
				}
			}
		}
		p++;
	}
}

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]);

	bfs();

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

	printf("%d\n", rez);

	return 0;
}