Cod sursa(job #76069)

Utilizator wefgefAndrei Grigorean wefgef Data 7 august 2007 19:23:29
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <cstdio>
#include <vector>

using namespace std;

#define sz(c) int((c).size())
#define pb push_back

#define Nmax 160

const int dx[] = {-1, 0, 1, 0},
	      dy[] = {0, 1, 0, -1};

int n, m, start;
int a[Nmax][Nmax];

vector<int> wait[Nmax*Nmax];
char viz[Nmax][Nmax];
char own[Nmax*Nmax];
int ret;

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

	scanf("%d %d %d", &n, &m, &start); --start;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			scanf("%d", &a[i][j]), --a[i][j];
}

void expand(int x, int y)
{
	if (viz[x][y]) return;

	int i, j, k;

	viz[x][y] = 1;
	++ret;

	if (++own[ x*m+y ] == 1)
		for (i = 0; i < sz(wait[ x*m+y ]); ++i)
			expand(wait[ x*m+y ][i]/m, wait[ x*m+y ][i]%m);

	for (k = 0; k < 4; ++k)
	{
		i = x + dx[k];
		j = y + dy[k];
		if (i >= 0 && i < n && j >= 0 && j < m)
			if (own[ a[i][j] ]) expand(i, j);
			else wait[ a[i][j] ].pb(i*m + j);
	}
}

int main()
{
	readdata();
	expand(start/m, start%m);
	printf("%d\n", ret);
	return 0;
}