Cod sursa(job #457419)

Utilizator loginLogin Iustin Anca login Data 19 mai 2010 17:12:49
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
# include <fstream>
# include <iostream>
# include <vector>
# include <algorithm>
# include <queue>
# define pb push_back
# define DIM 152
using namespace std;
struct poz{
	int i, j;
	poz(){}
	poz(int I, int J){
		i=I;j=J;}
};
int n, m, K, a[DIM][DIM], sol, key[DIM*DIM], di[4]={0, 0, -1,1}, dj[4]={-1, 1, 0, 0};
vector<poz>V[DIM*DIM];

void read ()
{
	ifstream fin ("castel.in");
	fin>>n>>m>>K;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			fin>>a[i][j];
}

int in_m (int i, int j)
{
	if (i && j && i<=n && j<=m)return 1;
	return 0;
}

void solve ()
{
	int i, j, ii, jj, kk;
	queue<poz>Q;
	if (K%m==0)i=K/m;
	else i=K/m+1;
	j=K-(i-1)*m;
	Q.push(poz(i, j));
	key[K]=1;
	a[i][j]=0;
	++sol;
	poz k;
	while (Q.size())
	{
		k=Q.front();
		Q.pop();
		i=k.i;
		j=k.j;
		for(int l=0;l<4;++l)
		{
			ii=i+di[l];
			jj=j+dj[l];
			if (in_m(ii, jj) && key[a[ii][jj]])
			{
				++sol;
				a[ii][jj]=0;
				kk=(ii-1)*m+jj;
				key[kk]=1;
				Q.push(poz(ii, jj));			
			}
			else
				if (in_m(ii, jj) && a[ii][jj])
					V[a[ii][jj]].pb(poz(ii, jj));
		}
		kk=(i-1)*m+j;
		for (vector<poz>::iterator I=V[kk].begin();I<V[kk].end();++I)
			if (a[I->i][I->j])
			{
				a[I->i][I->j]=0;
				++sol;
				key[(I->i-1)*m+I->j]=1;
				Q.push(poz(I->i, I->j));
			}
	}
}
		
int main()
{
	read ();
	solve ();
	ofstream fout ("castel.out");
	fout<<sol;
	return 0;
}