Cod sursa(job #123638)

Utilizator mithyPopovici Adrian mithy Data 16 ianuarie 2008 21:16:50
Problema Castel Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <cstdio>
#include <set>

using namespace std;

#define NMax 155

set <int> border;
int n, m, start, key[NMax][NMax], viz[NMax][NMax], keys[NMax*NMax], cam[NMax][NMax], startx, starty;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};


void read();
void solve();

int main()
{
	read();
	solve();
	return 0;
}

void read()
{
	int i, j;
	FILE *fin = fopen("castel.in", "rt");
	fscanf(fin, "%d %d %d", &n, &m, &start);
	for (i = 1; i <= n; i++)
		for (j = 1; j <= m; j++)
		{
			fscanf(fin, "%d", &key[i][j]);
			cam[i][j] = (i-1) * m + j;
			if ((i-1) * m + j == start)
			{
				startx = i;
				starty = j;
			}
		}
}

void solve()
{
	int go = 1, ok, i, j, x, k;
	//std::_Tree<_Traits>::iterator it;
	set<int>::iterator it;
	keys[start] = 1;
	viz[startx][starty] = 1;

	for (k = 0; k < 4; k++)
		border.insert(cam[startx+dx[k]][starty+dy[k]]);

	while (go)
	{
		go = 0;
		for (it = border.begin(),i=0; it != border.end(); it++)
		{
			x = *it;
			if (keys[key[(x-1)/m+1][(x-1)%m+1]])
			{
				ok = 0;
				for (k = 0; k < 4; k++)
					if (viz[(x-1)/m+1+dx[k]][(x-1)%m+1+dy[k]])
						ok = 1;				
				if (ok)
				{
					viz[(x-1)/m+1][(x-1)%m+1] = 1;
					keys[x] = 1;
					border.erase(it);
					it = border.begin();
					for (k = 0; k < 4; k++)
					{
						if (border.find(cam[(x-1)/m+1+dx[k]][(x-1)%m+1+dy[k]]) == border.end())
							if(!viz[(x-1)/m+1+dx[k]][(x-1)%m+1+dy[k]])
							{
								border.insert(cam[(x-1)/m+1+dx[k]][(x-1)%m+1+dy[k]]);
								go = 1;
							}
					}
				}
			}
		}
	}
	k = 0;
	for (i = 1; i <= n; i++)
		for (j = 1; j <= m; j++)
			k += viz[i][j];
	fprintf(fopen("castel.out", "wt"), "%d\n", k);
}