Cod sursa(job #88734)

Utilizator tudalexTudorica Constantin Alexandru tudalex Data 3 octombrie 2007 17:55:01
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <stdio.h>
#include <queue>
using namespace std;
const int maxim = 151*151+10;
const int dx[]={0,0,-1,1};
const int dy[]={-1,1,0,0};
queue <int> q,
			r[maxim];
int viz[maxim],
	v[maxim],
	a[maxim];
int i, j, m, n, sol, k;

inline int get_x(int x)
{
	if (x%m == 0)
		return (x/m);
	else
		return (x/m)+1;
}

inline int get_y(int x)
{
	return ((x-1)%m)+1;
}

inline int get_room(int x, int y)
{
	if (x <=n && x>0 && y<=m && y>0)
		return ((x-1)*m)+y;
	else
		return 0;
}

void merge_queue(int k)
{
	while (!r[k].empty())
	{
		q.push(r[k].front());
		r[k].pop();
	}
}

void process_room(int x)
{
	//viz[x] = 1;
	++sol;
	
	int o = get_x(x);
	int b = get_y(x);
	for (int i = 0; i < 4; ++ i)
	{
		int t = get_room(o+dx[i],b+dy[i]);
		if (!viz[t])
		{
			viz[t] = 1;
			if (!v[a[t]])
				r[a[t]].push(t);
			else
				q.push(t);
		}
	}
	if (v[x]==0)
	{
		v[x] = 1;
		merge_queue(x);
	}
}

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", &a[get_room(i,j)]);
	v[k] = 1;
	merge_queue(k);
	q.push(k);
	viz[k] = 1;
	viz[0] = 1;
	while (!q.empty())
	{
		process_room(q.front());
		q.pop();
	}
	printf("%d\n", sol);
	return 0;
}