Pagini recente » Cod sursa (job #869112) | Cod sursa (job #794001) | Cod sursa (job #1457554) | Cod sursa (job #799749) | Cod sursa (job #356661)
Cod sursa(job #356661)
#include<stdio.h>
#define infile "castel.in"
#define outfile "castel.out"
#define nmax 151
#define nnmax (nmax*nmax)
char v[nnmax]; //v[i]=1 daca camera i a fost vizitata
char w[nnmax]; //w[i]=1 daca camera i este in coada
int c[nnmax]; //coada
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
int nrc; //numarul de elemente din coada
int p; //pozitia ultimului element din coada
inline void add_coada(int x)
{
if(!w[x]) //daca nu exista deja in coada
{
c[(++p)%nnmax]=x; //il adaugam
nrc++; //crestem numarul de elemente din coada
w[x]=1; //il marcam ca adaugat
}
}
inline void add_vecini_coada(int x)
{
if(x-n>0 && !v[x-n]) add_coada(x-n); //deasupra
if(x+n<=n*m && !v[x+n]) add_coada(x+n); //dedesubt
if(x-1>0 && ((x-1)%n) && !v[x-1]) add_coada(x-1); //stanga
if(x+1<=n*m && (x%n) && !v[x+1]) add_coada(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(x); //adaugam vecinii in coada
}
void solve()
{
int j,k,nr2=0;
for(j=1;nrc;j++) //parcurgem coada cat timp avem elemente in ea
{
k=j%nnmax; //pozitia din coada circulara
if(!k) //daca s-a facut o parcurgere intreaga circulara
{
if(nr2==nr) //daca numarul de camere cu un pas in urma e egal cu numarul de camere de acum
break; //oprim, pentru ca nu s-a mai optimizat cu nimic
nr2=nr; //se schimba numarul de camere
}
w[c[k]]=0; //marcam ca nu se mai afla in coada
nrc--; //marcam ca s-a scos un element din coada
if(v[h[c[k]]] && !v[c[k]]) //daca pot intra in acesta camera, si nu am intrat inca
{
v[c[k]]=1; //marcam ca am intrat
nr++; //crestem numarul de camere vizitate
add_vecini_coada(c[k]); //adaugam vecinii in continuare in coada
}
else if(!v[c[k]]) add_coada(c[k]); //daca nu a fost rezolvat, il punem in coada cealalta
}
}
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;
}