Cod sursa(job #429705)

Utilizator funkydvdIancu David Traian funkydvd Data 30 martie 2010 13:23:55
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include<fstream>
#include<queue>
#include<vector>
#define pb push_back
#define mp make_pair
#define p push
#define A first
#define B second
#define PII pair<int,int>
using namespace std;
ifstream f("castel.in");
ofstream g("castel.out");
int n,m,k,s;
int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
int a[152][152],marc[152][152],key[152*152];
vector<PII> K[152*152];
queue<PII> Q;
void citire()
{
	f>>n>>m>>k;
	for (int i=1; i<=n; i++) 
		for (int j=1; j<=m; j++) f>>a[i][j];
}
void bordare()
{
	int i;
	for(i=1;i<=n;++i) a[i][0]=a[i][m+1]=n*m+1;
    for(i=1;i<=m;++i) a[0][i]=a[n+1][i]=n*m+1;
}
void make (int x, int y)
{
	int i;
	k=(x-1)*m+y;
	key[k]=1;
	for(vector<pair<int,int> >::iterator it=K[k].begin();it!=K[k].end();++it)
		marc[it->A][it->B]=2,Q.p(*it);
	K[a[x][y]].clear();
	for(i=0;i<4;++i)
		if(key[a[x+dx[i]][y+dy[i]]]==0)
			if(marc[x+dx[i]][y+dy[i]]==0)
			{
				marc[x+dx[i]][y+dy[i]]=1;
				K[a[x+dx[i]][y+dy[i]]].pb(mp(x+dx[i],y+dy[i]));
			}
			else;
		else
			if(marc[x+dx[i]][y+dy[i]]<=1)
			{
				marc[x+dx[i]][y+dy[i]]=2;
				Q.p(mp(x+dx[i],y+dy[i]));
			}
}
void init()
{
	Q.p(mp((k-1)/m+1,(k-1)%m+1));
    marc[(k-1)/m+1][(k-1)%m+1]=2;
}
void bfs()
{
	int x,y;
	 while(!Q.empty())
    {
        x=Q.front().A;
        y=Q.front().B;
        Q.pop();
        ++s;
		make (x,y);
    }
}
void afis()
{
	g<<s<<"\n";
}
int main()
{
    citire();
	bordare();
	init();
	bfs();
    afis();
    return 0;
}