Cod sursa(job #1150735)

Utilizator TudorMTudor Moldovanu TudorM Data 23 martie 2014 14:42:16
Problema Castel Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
#include<cstdio>
using namespace std;
FILE *f=fopen("castel.in","r");
FILE *g=fopen("castel.out","w");
int n,m,k,a[151][151],b[151][151],acc,d[151][151],l1,c1,dx[]={-1,0,1,0},dy[]={0,1,0,-1};
bool v[23000];
struct{int x,y;}c[23000];
struct{int x,y;bool bif;}lis[23000];
int interior(int x, int y)
{
    if(x<=n&&x>=1&&y<=m&&y>=1)return 1;
    return 0;
}
void citire()
{
    int i,j,numar=0;
    fscanf(f,"%d %d %d",&n,&m,&k);
    for(i=1;i<=n;++i)
    {
        for(j=1;j<=m;++j)
        {
            fscanf(f,"%d",&a[i][j]);
            ++numar;
            if(numar==k)
            {
                l1=i;
                c1=j;
            }
            d[i][j]=numar;
        }
    }
}
int lee(int x,int y)
{
    int xv,yv,u,p,i;
    u=p=1;
    c[u].x=x;
    c[u].y=y;
    b[x][y]=1;
    v[d[x][y]]=1;
    k=1;
    while(p<=u)
    {
        x=c[p].x;
        y=c[p++].y;
        for(i=0;i<=3;++i)
        {
            xv=x+dx[i];
            yv=y+dy[i];
            if(interior(xv,yv)&&b[xv][yv]<1&&v[a[xv][yv]])
            {
                c[++u].x=xv;
                c[u].y=yv;
                b[xv][yv]=b[x][y]+1;
                v[d[xv][yv]]=1;
            }
            else if(interior(xv,yv)&&b[xv][yv]==0)
            {
                lis[++k].x=xv;
                lis[k].y=yv;
                lis[k].bif=0;
                b[xv][yv]=-1;
            }
        }
        for(i=1;i<=k;++i)
        {
            if(lis[i].bif==0&&v[a[lis[i].x][lis[i].y]]&&b[lis[i].x][lis[i].y]==-1)
            {
                c[++u].x=lis[i].x;
                c[u].y=lis[i].y;
                lis[i].bif=1;
                b[lis[i].x][lis[i].y]=1;
                v[d[lis[i].x][lis[i].y]]=1;
            }
        }
    }
}
int main()
{
    int i, j;
    citire();
    lee(l1,c1);
    for(i=1;i<=n;++i)
    {
        for(j=1;j<=m;++j)if(b[i][j]>0)++acc;
    }
    fprintf(g,"%d",acc);
    fclose(f);
    fclose(g);
    return 0;
}