Pagini recente » Cod sursa (job #3156173) | Cod sursa (job #3187444) | Cod sursa (job #459081) | Cod sursa (job #2972650) | Cod sursa (job #356865)
Cod sursa(job #356865)
#include<stdio.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
struct lista *p; //pozitia lu fratesu
} *l[nnmax]; //l[i]-lista camerelor ce au nevoie de camera i
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
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(struct lista *l, int x)
{
struct lista *n=malloc(sizeof(struct lista)); //creeam spatiu pt noul nod din lista
n->v=x; //salvam valoarea
n->p=l;
l=n;
}
inline void vecin(int x)
{
if(v[h[x]]) push_coada(x); //daca poate intra in coada, il adaugam in camera
else push_lista(l[h[x]],x); //il adaugam in lista camerelor ce au nevoie de cheia e 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()
{
push_coada(x); //adaugam in coada pozitia in care se afla initial
}
void solve()
{
int x;
while(c.p<=c.q)
{ //cat timp avem elemente in coada de rezolvat
x=pop_coada(); //luam nodul ce tebuie rezolvat
//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] && !v[x+1]) vecin(x+1); //dreapta
//acum parcurgem lista camerelor ce au nevoie de aceasta cheie
while(l[x])
{
push_coada(l[x]->v);
l[x]=l[x]->p;
}
}
}
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;
}