Cod sursa(job #356911)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 17 octombrie 2009 14:42:33
Problema Castel Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 2.17 kb
#include<stdio.h>
#include<malloc.h>
#define infile "castel.in"
#define outfile "castel.out"
#define nmax 151
#define nnmax (nmax*nmax)
struct coada
{
	int c[nnmax]; //coada
	int p,q; //cele doua capete
} c; //coada
struct lista
{
	int v; //valoarea
	int p; //pozitia lu fratesu
} l[nnmax]; //aici vor fi salvate informatiile din lista
int p[nnmax]; //pozitia catre lista
int h[nnmax]; //harta castelului
char v[nnmax]; //v[i]=1 daca camera i a fost deschisa
char w[nnmax]; //w[i]=1 daca camera i se afla intr-o lista
int m,n; //numarul de linii, respectiv coloane
int x; //pozitia innitialia a printesei
int nr; //numarul de camere deschise
int nrl; //numarul de elemente din lista

inline void push_coada(int x)
{
	c.c[++c.q]=x; //punem in coada
	v[x]=1; //marcam camera ca atinsa
	nr++; //crestem numarul de camere
}

inline int pop_coada()
{
	return c.c[c.p++];
}

inline void push_lista(int poz, int x)
{
	nrl++; //facem loc in lista
	l[nrl].v=x;
	l[nrl].p=p[poz];
	p[poz]=nrl;
	w[x]=1; //marcam ca este in lista
}

inline void vecin(int x)
{
	if(v[h[x]]) push_coada(x); //daca poate intra in camera, il adaugam in coada
	else push_lista(h[x],x); //il adaugam in lista camerelor ce au nevoie de cheia pe care are nevoie si el
}

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()
{
	c.p=1; //initializam coada
	push_coada(x); //adaugam in coada pozitia in care se afla initial
}

void solve()
{
	int i,x;
	while(c.p<=c.q)
	{ //cat timp avem elemente in coada de rezolvat
		x=pop_coada(); //luam nodul ce tebuie rezolvat
		
		//acum parcurgem lista camerelor ce au nevoie de aceasta cheie
		for(i=p[x];i;i=l[i].p)
			push_coada(l[i].v);
		
		//verificam fiecare vecin al lui
		if(x-n>0 && !v[x-n] && !w[x-n]) vecin(x-n); //deasupra
		if(x+n<=n*m && !v[x+n] && !w[x+n]) vecin(x+n); //dedesubt
		if(x-1>0 && ((x-1)%n) && !v[x-1] && !w[x-1]) vecin(x-1); //stanga
		if(x+1<=n*m && (x%n) && !v[x+1] && !w[x+1]) vecin(x+1); //dreapta
	}
}

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

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