Cod sursa(job #1490617)

Utilizator LegionHagiu Stefan Legion Data 23 septembrie 2015 21:16:08
Problema Castel Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int camera[155][155];
bool gasit[155 * 155];
vector<int> deexplorat[155 * 155];
 int n, m;
void rez(int k)
{
	vector<int> coada;
	ofstream out("castel.out");
	int i,x,y,j,t=0;
	coada.push_back(k);
	for (i = 0; i < coada.size(); i++)
	{
		x = coada[i];
		y = x%n;
		if (x>0)
		x = x / n;
		if (gasit[x*n + y] == 0)
		{
			t++;
			gasit[x*n + y] = 1;
		}
		for (j = 0; j<deexplorat[x*n + y].size(); j++)
		{
			coada.push_back(deexplorat[x*n + y][j]);
		}
		if (x>0 && gasit[(x-1)*n + y] == 0)
		{
			if (gasit[camera[x - 1][y]] == 0)
			{
				deexplorat[camera[x - 1][y]].push_back((x - 1)*n + y);
			}
			else
			{
				coada.push_back((x - 1)*n + y);
			}
		}
		if (x<n && gasit[(x+1)*n + y] == 0)
		{
			if (gasit[camera[x + 1][y]] == 0)
			{
				deexplorat[camera[x + 1][y]].push_back((x + 1)*n + y);
			}
			else
			{
				coada.push_back((x + 1)*n + y);
			}
		}
		if (y > 0 && gasit[x*n + y - 1] == 0)
		{
			if (gasit[camera[x][y - 1]] == 0)
			{
				deexplorat[camera[x][y - 1]].push_back(x*n + y - 1);
			}
			else
			{
				coada.push_back(x*n + y - 1);
			}
		}
		if (y <m && gasit[x*n + y + 1] == 0)
		{
			if (gasit[camera[x][y + 1]] == 0)
			{
				deexplorat[camera[x][y + 1]].push_back(x*n + y + 1);
			}
			else
			{
				coada.push_back(x*n + y + 1);
			}
		}
	}
	out << t;
}
int main()
{
	ifstream in("castel.in");
	int i, j, k;
	in >> n;
	in >> m;
	in >> k;
	n--;
	m--;
	k--;
	for (i = 0; i <= n; i++)
	{
		for (j = 0; j <= m; j++)
		{
			in >> camera[i][j];
			camera[i][j]--;
		}
	}
	rez(k);
}