Cod sursa(job #355445)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 11 octombrie 2009 10:20:34
Problema Castel Scor 10
Compilator c Status done
Runda Arhiva de probleme Marime 2.71 kb
#include<stdio.h>
#define infile "castel.in"
#define outfile "castel.out"
#define nmax 151
#define nnmax (nmax*nmax)
struct coada
{
	int c[nnmax]; //aici se salveaza elementele cozii
	int n; //numarul de elemente din coada
} a,b; //a-coada cu camerele in care urmeaza sa intru (dar nu stiu sigur daca am cheie), b-coada cu camerele in care ot ajunge, dar inca nu am cheie
char c[nnmax]; //c[i]=1 daca prizonierul are cheia i, si automat daca are cheia i, inseamna ca a si vizitat amera i
char v[nnmax]; //v[i]=1 daca camera i se afla in coada a
int h[nnmax]; //harta cheilor ce se gasesc in fiecare camera
int m,n; //numarul de linii respectiv coloane
int k; //camera in care se afla prizonierul
int nr; //numarul de camere pe care le-a vizitat

inline void add_coada(int c[nnmax], int *n, int x)
{
	*n+=1;
	c[*n]=x;
}

inline void add_vecini_coada(int x)
{ //toti vecinii se pot adauga doar in coada a, deoarece doar aici sunt toti
	if(x-n>0 && !c[x-n] && !v[x-n]) { v[x-n]=1; add_coada(a.c,&a.n,x-m); } //deasupra
	if(x+n<=n*m && !c[x+n] && !v[x+n]) { v[x+n]=1; add_coada(a.c,&a.n,x+n); } //dedesubt
	if(x-1>0 && ((x-1)%n) && !c[x-1] && !v[x-1]) { v[x-1]=1; add_coada(a.c,&a.n,x-1); } //stanga
	if(x+1<=n*m && (x%n) && !c[x+1] && !v[x+1]) { v[x+1]=1; add_coada(a.c,&a.n,x+1); } //dreapta
}

inline void parcurg_coada_a()
{
	int i;
	for(i=1;i<=a.n;i++) //elementele din coada
		if(!c[a.c[i]]) //daca nu a fost cumva deja rezolvat
		{
			if(c[h[a.c[i]]]) //daca am cheia camerei
			{
				c[a.c[i]]=1; //marcam aceasta camera
				nr++; //crestem deci si numarul de camere vizitate
				add_vecini_coada(a.c[i]); //si ii adaugam vecinii in coada
			}
			else add_coada(b.c,&b.n,a.c[i]); //il punem in coada cealalta
			v[a.c[i]]=0; //il marcam ca nu se mai afla in coada a
		}
	a.n=0; //golim coada a
}

inline void mut_in_coada_a()
{ //mut elementele din coada b in coada a
	int i;
	for(i=1;i<=b.n;i++)
		if(!c[b.c[i]]) //daca nu a fost deja rezolvavt
		{
			add_coada(a.c,&a.n,b.c[i]);
			v[b.c[i]]=1; //il marcam ca se afla in coada
		}
	b.n=0; //golim coada b
}

void read()
{
	int i,j;
	scanf("%d %d %d\n",&m,&n,&k);
	for(i=1;i<=m;i++)
		for(j=1;j<=n;j++)
			scanf("%d",&h[(i-1)*n+j]);
}

void init()
{
	c[k]=1; //avem cheia camerei in care ne aflam
	nr=1; //avem deci o camera vizitata
	add_vecini_coada(k); //adaugam vecinii in coada
}

void solve()
{
	int nr_ant=0;
	while(nr_ant<nr)
	{ //cat timp cu o data in urma am obtinut mai putin
		nr_ant=nr; //ne salvam data din urma
		parcurg_coada_a();
		mut_in_coada_a();
	}
}

void write()
{
	int i,nr=0;
	for(i=1;i<=n*m;i++)
		if(c[i])
			nr++;
	printf("%d\n",nr);
}

int main()
{
	freopen(infile,"r",stdin);
	freopen(outfile,"w",stdout);
	
	read();
	init();
	solve();
	write();
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}