Cod sursa(job #161823)

Utilizator slayer4uVictor Popescu slayer4u Data 18 martie 2008 20:52:16
Problema Castel Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 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[151];
long i, j, ni, nj, inc, sf, n, m, k, sx, sy, num;


void expand(long i, long j)
{
//	printf("\n\nexpanding (%ld,%ld).. \n\n", i, j);
	visit[i][j] = 1;
	chei_ihave[(i - 1) * m + j] = 1;
	chei[++sf] = (i - 1) * m + 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 (!visit[ni][nj])
			{
//				printf(" -- (%ld, %ld) not visited -- ", ni, nj);
				if (!chei_ihave[x[ni][nj]])
				{
//					printf(">> nam %ld << ", x[ni][nj]);
//					next[x[ni][nj]][++next[x[ni][nj]][0]] = (ni - 1) * m + nj;
					next[x[ni][nj]].push_back((ni - 1) * m + 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;
	sx = k / m + 1;
	sy = k % m;
	expand(sx, sy);
	while (inc <= sf)
	{
		k = chei[inc];
		for (i = 0; i < next[k].size(); ++i)
		{
			ni = next[k][i] / m + 1;
			nj = next[k][i] % m;
			expand(ni, nj);
		}
		++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