Cod sursa(job #161861)

Utilizator slayer4uVictor Popescu slayer4u Data 18 martie 2008 21:28:43
Problema Castel Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <stdio.h>
#include <vector>
using namespace std;

const long MAX =  151 * 151;

long dx[] = {0, 1, 0, -1, 0};
long dy[] = {0, 0, 1,  0,-1};
long chei_ihave[MAX], chei[MAX];
long x[151][151], visit[151][151];
vector <long> next[MAX];
long i, j, ni, nj, inc, sf, n, m, k, sx, sy, num;

inline long yy(long node)
{
	return node % m == 0 ? m : node % m;
}

inline long xx(long node)
{
	return node / m + 1;
}

inline long node(int i, int j) 
{
	return (i - 1) * m + j;
}

void expand(long i, long j)
{
//	printf("\n\nexpanding (%ld,%ld).. \n\n", i, j);
	if (visit[i][j] == 1)
		return;
	visit[i][j] = 1;
	chei[++sf] = node(i, j);
	for (long a = 1; a <= 4; ++a)
	{
		ni = i + dx[a];
		nj = j + dy[a];
		if (ni >= 1 && ni <= n && nj >= 1 && nj <= m)
		{
//			printf("attempting (%ld, %ld); ", ni, nj);
			if (!chei_ihave[x[ni][nj]])
			{
//				printf(" -- (%ld, %ld) not visited -- ", ni, nj);
				if (!visit[ni][nj])
				{
//					printf(">> nam %ld << ", x[ni][nj]);
					next[x[ni][nj]].push_back(node(ni, nj));
					visit[ni][nj] = 2;
				}
			}
			else
				expand(ni, nj);
		}

	}
}

int main()
{
	freopen ("castel.in", "rt", stdin);
	freopen ("castel.out", "wt", stdout);

	scanf("%ld %ld %ld", &n, &m, &k);

	for (i = 1; i <= n; ++i)
		for (j = 1; j <= m; ++j)
			scanf("%ld", &x[i][j]);

	inc = 1;
//	printf("k = %d\n", k);
	expand(xx(k), yy(k));
	while (inc <= sf)
	{
		k = chei[inc];
		chei_ihave[k] = 1;
		for (i = 0; i < next[k].size(); ++i)
		{
			expand(xx(next[k][i]), yy(next[k][i]));
		}
		++inc;
	}

	for (i = 1; i <= n; ++i)
		for (j = 1; j <= m; ++j)
			num = visit[i][j] == 1 ? num + 1 : num;

	printf("%ld\n", num);

	return 0;
}

// x[i][j] = (i - 1) * n + j