Mai intai trebuie sa te autentifici.
Cod sursa(job #429061)
Utilizator | Data | 29 martie 2010 19:59:55 | |
---|---|---|---|
Problema | Castel | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.47 kb |
#include<cstdio>
const int nmax=1<<8;
bool f[nmax*nmax],ver[nmax][nmax];
int rez,u,n,m,k,cx[nmax*nmax],cy[nmax*nmax],nec[nmax][nmax];
int dl[]={0,1,0,-1};
int dc[]={1,0,-1,0};
void bordare()
{
for(int i=0;i<=n+1;i++)
ver[i][0]=ver[i][m+1]=true;
for(int j=0;j<=m+1;j++)
ver[0][j]=ver[n+1][j]=true;
}
int camera(int x,int y)
{
return (x-1)*m+y;
}
void citire()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&nec[i][j]);
u++;
cx[u]=(k-1)/m+1;
cy[u]=k-(cx[u]-1)*m;
ver[cx[u]][cy[u]]=true;
rez=1;
f[camera(cx[u],cy[u])]=true;
bordare();
}
void bfs()
{
bool ok=true;
int ant=0;
int act,x,y;
x=y=0;
while(ok)
{
act=u;
ok=false;
for(int i=ant+1;i<=act;i++)
for(int j=0;j<4;j++)
{
x=cx[i]+dl[j];
y=cy[i]+dc[j];
if(!ver[x][y] && f[nec[x][y]])
{
u++;
cx[u]=x;
cy[u]=y;
f[camera(cx[u],cy[u])]=true;
ver[cx[u]][cy[u]]=true;
rez++;
ok=true;
}
}
if(!ok)
{
for(int i=1;i<=u;i++)
for(int j=0;j<4;j++)
{
x=cx[i]+dl[j];
y=cy[i]+dc[j];
if(!ver[x][y] && f[nec[x][y]])
{
u++;
cx[u]=x;
cy[u]=y;
f[camera(cx[u],cy[u])]=true;
ver[cx[u]][cy[u]]=true;
rez++;
ok=true;
}
}
}
ant=act;
}
}
int main()
{
freopen("castel.in","r",stdin);
freopen("castel.out","w",stdout);
citire();
bfs();
printf("%d",rez);
return 0;
}