Cod sursa(job #891807)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 25 februarie 2013 20:16:12
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.15 kb

#include <cstdio>
#include <vector>
#include <algorithm>

const int MAX_SIZE(152);

int m, n, k;

struct coord
{
	int i;
	int j;
};

int matrix [MAX_SIZE] [MAX_SIZE];
std::vector<std::pair<int,int> > closed [MAX_SIZE * MAX_SIZE];
struct coord queue [MAX_SIZE * MAX_SIZE];
bool mark [MAX_SIZE * MAX_SIZE];
bool open [MAX_SIZE] [MAX_SIZE];

inline void read (void)
{
	std::freopen("castel.in","r",stdin);
	std::scanf("%d %d %d",&m,&n,&k);
	int i, j;
	for (i = 1 ; i <= m ; ++i)
		for (j = 1 ; j <= n ; ++j)
			std::scanf("%d",&matrix[i][j]);
	std::fclose(stdin);
}

inline void print (void)
{
	int i, j, result(0);
	for (i = 1 ; i <= m ; ++i)
		for (j = 1 ; j <= n ; ++j)
			if (open[i][j])
				++result;
	std::freopen("castel.out","w",stdout);
	std::printf("%d\n",result);
	std::fclose(stdout);
}

inline int number (int i, int j)
{
	return (i - 1) * n + j;
}

inline struct coord position (int k)
{
	struct coord p;
	p.i = (k - 1) / n + 1;
	if (k % n)
		p.j = k % n;
	else
		p.j = n;
	return p;
}

inline void BreadthFirstSearch (void)
{
	const int WAY(4);
	const int X [ ] = {-1,0,1,0};
	const int Y [ ] = {0,1,0,-1}; 
	struct coord *push(queue + 1), *pop(queue);
	*queue = position(k);
	mark[number(queue->i,queue->j)] = true;
	matrix[queue->i][queue->j] = 0;
	open[queue->i][queue->j] = true;
	int i, j, x, y, z, a, b, end;
	while (pop < push)
	{
		i = pop->i;
		j = pop->j;
		b = number(i,j);
		if (closed[b].size())
		{
			for (a = 0, end = closed[b].size() ; a < end ; ++a)
			{
				push->i = closed[b][a].first;
				push->j = closed[b][a].second;
				matrix[push->i][push->j] = 0;
				open[push->i][push->j] = true;
				mark[number(push->i,push->j)] = true;
				++push;
			}
			closed[b].clear();
		}
		for (z = 0 ; z < WAY ; ++z)
		{
			x = i + X[z];
			y = j + Y[z];
			if (matrix[x][y])
			{
				if (!mark[matrix[x][y]])
				{
					closed[matrix[x][y]].push_back(std::make_pair(x,y));
					matrix[x][y] = 0;
				}
				else
				{
					push->i = x;
					push->j = y;
					++push;
					open[x][y] = true;
					matrix[x][y] = 0;
					if (!mark[number(x,y)])
						mark[number(x,y)] = true;
				}
			}
		}
		++pop;
	}
}

int main (void)
{
	read();
	BreadthFirstSearch();
	print();
	return 0;
}