Cod sursa(job #302868)

Utilizator laserbeamBalan Catalin laserbeam Data 9 aprilie 2009 12:55:31
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
/* BALAN CATALIN - CASTEL - INFOARENA */
/*
Variabile:
what[i] - ce cheie trebuie pentru a deschide camera i
key[i] - lista camerelor care se deschid cu cheia i
acces[i] - primul bit -> pot intra in camera desi s-ar putea sa n-am cheia
			- al 2-lea bit -> am intrat deja in camera si am cheia i
*/
#include<cstdio>
#include<vector>
#include<queue>
#define NMMAX 22501
using namespace std;
vector<int> key[NMMAX];
queue<int> camere;
int acces[NMMAX],what[NMMAX];
int dir, OX[4] = {0,1,0,-1}, OY[4] = {1,0,-1,0}, nrcamere, n, m;
char buf[1024],*p;
int get()
{
	for (;*p==' ';++p);
	int t;
	for (t=0; *p>='0' && *p<='9';++p)t=t*10 + *p-'0';
	return t;
}

void verifica(int cheie)
{
	for (int i = 0; i < key[cheie].size(); ++i)
	{
		if ((acces[key[cheie][i]]&3)==1)
		{
			nrcamere++;
			acces[key[cheie][i]]=3;
			camere.push(key[cheie][i]);
		}
	}
}

int main()
{
int i,j,k,start,now,next,x,xx,y,yy;
FILE *f = fopen("castel.in","r");
fscanf(f,"%d %d %d\n",&n,&m,&start);
for (i = 0, k = 0; i < n; ++i)
{
	fgets(buf,sizeof(buf),f);p=buf;
	for (j = 0; j < m; ++j, ++k)
	{
		what[k]=get();
		what[k]--;
		key[what[k]].push_back(k);
	}
}
camere.push(--start);
fclose(f);
acces[start]=3;
nrcamere=1;
while(!camere.empty())
{
	now = camere.front();
	camere.pop();
	verifica(now);
	x = now/m;
	y = now%m;
	for (dir = 0; dir < 4; ++dir)
	{
		xx = x+OX[dir];
		yy = y+OY[dir];
		next = xx*m+yy;
		if (xx>=0 && xx<n && yy>=0 && yy<m && (acces[next]&2)==0)
		{
			if ((acces[what[next]]&2)==2)
			{
				acces[next]=3;
				camere.push(next);
				nrcamere++;
			}
			else
			{
				acces[next]=1;
			}
		}
	}
}

FILE *g = fopen("castel.out","w");
fprintf(g,"%d\n",nrcamere);
fclose(g);

return 0;
}