Cod sursa(job #340133)

Utilizator savimSerban Andrei Stan savim Data 13 august 2009 12:03:36
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <stdio.h>
#include <vector>

using namespace std;

#define MAX_N 160
#define MAX_L 22510

int n, m, k, nr, st, dr;
int A[MAX_N][MAX_N], mat[MAX_N][MAX_N];
int key[MAX_L];

int lee[2][MAX_L];
int d[4] = {0, 0, -1, 1};

vector <int> v[MAX_L];

inline int cor_l(int p, int q) {
	return (p - 1) * m + q;
}

void cit() {
	freopen("castel.in", "r", stdin);
	freopen("castel.out", "w", stdout);

	scanf("%d %d %d", &n, &m, &k);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			scanf("%d", &A[i][j]);	
			v[A[i][j]].push_back(cor_l(i, j));
		}
}

inline int cor_x(int p) {
	if (p % m) return p / m + 1;
	else return p / m;
}

inline int cor_y(int p) {
	if (p % m) return p % m;
	else return m;
}

void lee_algo(int p, int q) {
	int l = 0, r = 1;
	lee[0][1] = p;
	lee[1][1] = q;

	if (mat[p][q] == 2) {
		mat[p][q] = 1; 
		key[++dr] = cor_l(p, q);
	}

    while (l < r) {
		l++;
		for (int i = 0; i < 4; i++) {
			int x = lee[0][l] + d[i];
			int y = lee[1][l] + d[3 - i];

			if (mat[x][y] == 2) {
				lee[0][++r] = x;
				lee[1][r] = y;

				mat[x][y] = 1;
				key[++dr] = cor_l(x, y);
			}
		}
	}
}

void solve() {
	nr = 1; key[1] = k;
	mat[cor_x(k)][cor_y(k)] = 1;

	st = 0; dr = 1;
	while (st < dr) {
    	st++;
		k = key[st];

		int len = v[k].size();

		for (int i = 0; i < len; i++) {
        	int x = cor_x(v[k][i]);
			int y = cor_y(v[k][i]);
			int ok = 0;

			if (!mat[x][y]) mat[x][y] = 2;
			for (int j = 0; j < 4; j++) {
				int NewX = x + d[j];
				int NewY = y + d[3 - j];

				if (mat[NewX][NewY] == 1) ok = 1;
			}

			if (ok)
				lee_algo(x, y);
		}
	}
}

void write() {
	int nr = 0;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (mat[i][j] == 1) nr++;

	printf("%d\n", nr);
}

int main() {

	cit();
	solve();
	write();

	return 0;
}