Cod sursa(job #356648)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 15 octombrie 2009 18:23:20
Problema Castel Scor 50
Compilator c Status done
Runda Arhiva de probleme Marime 2.63 kb
#include<stdio.h>
#define infile "castel.in"
#define outfile "castel.out"
#define nmax 151
#define nnmax (nmax*nmax)
struct coada
{
	char v[nnmax]; //vector de vizite, pt a sti daca se afla deja in coada
	int c[nnmax]; //coada
	int n; //numarul de elemente din coada
	int p; //pozitia ultimului element din coada
} c[2];
char v[nnmax]; //v[i]=1 daca camera i a fost vizitata
int h[nnmax]; //harta
int m,n; //numarul de linii, respectiv coloane
int x; //camera in care se afla printesa
int nr; //numarul de camere pe care le poate deschide printesa

inline void add_coada(char v[nnmax], int c[nnmax], int *nr, int *p, int x)
{
	if(!v[x]) //daca nu exista deja in coada
	{
		c[(++(*p))%nnmax]=x; //il adaugam
		(*nr)++; //crestem numarul de elemente din coada
		v[x]=1; //il marcam ca adaugat
	}
}

inline void add_vecini_coada(char v[nnmax],  int c[nnmax], int *nr, int *p, int x)
{
	if(x-n>0 && !v[x-n]) add_coada(v,c,nr,p,x-n); //deasupra
	if(x+n<=n*m && !v[x+n]) add_coada(v,c,nr,p,x+n); //dedesubt
	if(x-1>0 && ((x-1)%n) && !v[x-1]) add_coada(v,c,nr,p,x-1); //stanga
	if(x+1<=n*m && (x%n) && !v[x+1]) add_coada(v,c,nr,p,x+1); //dreapta
}

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

void init()
{
	v[x]=1; //marcam ca vizitata camera initiala
	nr++; //crestem camerele vizitate
	add_vecini_coada(c[0].v,c[0].c,&c[0].n,&c[0].p,x); //adaugam vecinii in coada
}

void solve()
{
	int i,ii,ii1,j,k,nr2=0;
	for(i=0;nr2<nr;i++) //cat timp numarul total anterior este mai mic decat numarul total curent
	{ //i-este folosit pentru a sti cu care coada lucram ;))
		ii=i%2; ii1=(i+1)%2; //le calculam de acum, a.i. sa nu mai calculam de fiecare data
		nr2=nr; //numarul curent devine anterior
		c[ii1].n=c[ii1].p=0; //coada cealalta devine nulla
		for(j=1;c[ii].n;j++) //parcurgem coada cat timp avem elemente in ea
		{
			k=j%nnmax;
			if(v[h[c[ii].c[k]]] && !v[c[ii].c[k]]) //daca pot intra in acesta camera, si nu am intrat inca
			{
				v[c[ii].c[k]]=1; //marcam ca am intrat
				nr++; //crestem numarul de camere vizitate
				add_vecini_coada(c[ii].v, c[ii].c,&c[ii].n,&c[ii].p,c[ii].c[k]); //adaugam vecinii in continuare in coada
			}
			else if(!v[c[ii].c[k]]) add_coada(c[ii1].v, c[ii1].c, &c[ii1].n, &c[ii1].p, c[ii].c[k]); //daca nu a fost rezolvat, il punem in coada cealalta
			
			c[ii].v[c[ii].c[k]]=0; //marcam ca nu se mai afla in coada
			c[ii].n--; //marcam ca s-a scos un element din coada
		}
	}
}

void write()
{
	printf("%d\n",nr);
}

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