Cod sursa(job #1602802)

Utilizator Julian.FMI Caluian Iulian Julian. Data 16 februarie 2016 22:19:27
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <iostream>
#include <fstream>
#include <stdlib.h>
#define nmax 160
using namespace std;
ifstream fin("castel.in");
ofstream fout("castel.out");


int a[nmax*nmax],viz[nmax*nmax],q[60000];
int *l[nmax*nmax],inq[nmax*nmax];

int main()
{int start,i,j,n,m;
    fin>>n>>m;
    fin>>start;
    for(i=1;i<=n*m;i++)
        {fin>>a[i];
        l[i]=(int*)realloc(l[i],sizeof(int));
        l[i][0]=0;
        }



long in,sf;
int x,v;
long rezultat=1;
in=sf=0;
q[in]=start;
viz[start]=1;
    while(in<=sf)
    {x=q[in++];
        for(i=1;i<=l[x][0];i++)
        {if(!viz[l[x][i]])rezultat++;
            viz[l[x][i]]=1;

         if(!inq[l[x][i]]){q[++sf]=l[x][i];inq[l[x][i]]=1;}
        }

        //toti vecinii:
        v=x-m;
        if(v>0)
            if(!viz[v])
                if(viz[a[v]])
                {viz[v]=1;
                 q[++sf]=v;rezultat++;
                }
                else {
                    l[a[v]][0]++;
                    l[a[v]]=(int*)realloc(l[a[v]],(l[a[v]][0]+1)*sizeof(int));
                    l[a[v]][l[a[v]][0]]=v;
                }

        v=x+m;
        if(v<=n*m)
            if(!viz[v])
                if(viz[a[v]])
                {viz[v]=1;
                 if(!inq[v]){q[++sf]=v;inq[v]=1;}
                 rezultat++;
                }
                else {
                    l[a[v]][0]++;
                    l[a[v]]=(int*)realloc(l[a[v]],(l[a[v]][0]+1)*sizeof(int));
                    l[a[v]][l[a[v]][0]]=v;
                }
        v=x+1;
        if(v%m!=1)
            if(!viz[v])
                if(viz[a[v]])
                {viz[v]=1;
                 if(!inq[v]){q[++sf]=v;inq[v]=1;}
                 rezultat++;
                }
                else {
                    l[a[v]][0]++;
                    l[a[v]]=(int*)realloc(l[a[v]],(l[a[v]][0]+1)*sizeof(int));
                    l[a[v]][l[a[v]][0]]=v;
                }
        v=x-1;
        if(v%m!=0)
            if(!viz[v])
                if(viz[a[v]])
                {viz[v]=1;rezultat++;
                 if(!inq[v]){q[++sf]=v;inq[v]=1;}
                }
                else {
                    l[a[v]][0]++;
                    l[a[v]]=(int*)realloc(l[a[v]],(l[a[v]][0]+1)*sizeof(int));
                    l[a[v]][l[a[v]][0]]=v;
                }

    inq[x]=0;
    }
fout<<rezultat;


}