Cod sursa(job #1154779)

Utilizator george_stelianChichirim George george_stelian Data 26 martie 2014 13:20:25
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <cstdio>
#include <vector>
#define pb push_back

using namespace std;

vector<int> v[23000];
vector<int>::iterator it;
int chei[23000],camere[23000],v1[23000],posibil[23000],nr,nr1,nraux,a,sol,x,n,m,i,j,k;

int uiteteinjur(int x)
{
    if(x>m && posibil[x-m]==2) return 2;
    if(x%m && posibil[x+1]==2) return 2;
    if(posibil[x+m]==2) return 2;
    if(x%m!=1 && posibil[x-1]==2) return 2;
    return 1;
}
void phil(int x)
{
    sol++;
    chei[++nr]=x;
    posibil[x]=2;
    if(x>m && posibil[x-m]==1) phil(x-m);
    if(x%m && posibil[x+1]==1) phil(x+1);
    if(posibil[x+m]==1) phil(x+m);
    if(x%m!=1 && posibil[x-1]==1) phil(x-1);
}

int main()
{
    freopen("castel.in", "r", stdin);
    freopen("castel.out", "w", stdout);
    scanf("%d%d%d",&n,&m,&k);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            scanf("%d",&v1[(i-1)*m+j]);
            if((i-1)*m+j!=k) v[v1[(i-1)*m+j]].pb((i-1)*m+j);
        }
    posibil[k]=2;
    nr1=nr=sol=1;
    chei[nr]=v1[k];
    while(nr1<=nr)
    {
        nraux=nr+1;
        a=0;
        for(i=nr1;i<=nr;i++)
            for(it=v[chei[i]].begin();it!=v[chei[i]].end();it++)
            {
                x=*it;
                posibil[x]=uiteteinjur(x);
                if(posibil[x]==2) camere[++a]=x;
            }
        for(i=1;i<=a;i++)
			phil(camere[i]);
        nr1=nraux;
    }
    printf("%d",sol);
    return 0;
}