Cod sursa(job #680560)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 15 februarie 2012 19:05:50
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include<fstream>
#include<vector>
#include<queue>
#define NMAX 160

using namespace std;

ifstream f("castel.in");
ofstream g("castel.out");

int a[NMAX][NMAX], n, m, k, nr=0;
int di[4]={0, 0, -1, 1};
int dj[4]={-1, 1, 0, 0};
bool chei[22501], vz[NMAX][NMAX], ad[NMAX][NMAX];

queue<int> q;
vector<int> v[22501];

void Citeste()
{
	int i, j;
	f>>n>>m>>k;
	for (i=1; i<=n; ++i)
		for (j=1; j<=m; ++j) f>>a[i][j];
	for (i=0; i<=n+1; ++i) a[i][0]=a[i][m+1]=-1;
	for (j=0; j<=m+1; ++j) a[0][j]=a[n+1][j]=-1;
}

void Adauga(int i, int j)
{
	int k, val=(i-1)*m+j;
	++nr;
	vz[i][j]=1; chei[val]=1; q.push(i*1000+j);
	for (k=0; k<(int)v[val].size(); ++k) Adauga(v[val][k]/1000, v[val][k]%1000);
}

void Solve()
{
	int sti, stj, r, i, j, ii, jj, kk;
	sti=k/m;
	if (k%m!=0) sti++;
	stj=k%m;
	if (stj==0) stj=m;
	Adauga(sti, stj);
	while(!q.empty())
	{
		r=q.front(); q.pop();
		i=r/1000; j=r%1000;
		for (kk=0; kk<4; ++kk)
		{
			ii=i+di[kk]; jj=j+dj[kk];
			if (!vz[ii][jj] && a[ii][jj]>0)
				if (chei[a[ii][jj]]) Adauga(ii, jj);
				else
					if (!ad[ii][jj])
					{
						v[a[ii][jj]].push_back(ii*1000+jj);
						ad[ii][jj]=1;
					}
		}
	}
	g<<nr<<"\n";
}

int main()
{
	Citeste();
	Solve();
	f.close();
	g.close();
	return 0;
}