Cod sursa(job #546199)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 4 martie 2011 16:25:48
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include<stdio.h>
#include<vector>
using namespace std;

#define mp make_pair
#define x first
#define y second
#define NMAX 157

vector < pair<int,int> > v[NMAX*NMAX];
int n,m,k,nr,sol;
int a[NMAX][NMAX];
int g[NMAX][NMAX];
int viz[NMAX][NMAX];
int ch[NMAX*NMAX];
pair<int,int> q[NMAX*NMAX];
int inc,sf;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};

void actual(int key)
{
    int i,lim=v[key].size();
    pair <int,int> p;
    
    for(i=0;i<lim;i++)
    {
        p=v[key][i];
        q[++sf]=p;
        viz[p.x][p.y]=1;
        ch[g[p.x][p.y]]=1;
        actual(g[p.x][p.y]);
    }
}

int main ()
{
    int i,j;
    int px,py,sx,sy;
    
    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",&a[i][j]);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            g[i][j]=++nr;
            if(nr==k)
            {
                q[1]=mp(i,j);
                viz[i][j]=1;
                ch[nr]=1;
            }
        }
    inc=1;sf=1;
    while(inc<=sf)
    {
        px=q[inc].x;
        py=q[inc].y;
        for(i=0;i<4;i++)
        {
            sx=px+dx[i];
            sy=py+dy[i];
            if(viz[sx][sy] || sx<1 || sx>n || sy<1 || sy>m)
                continue;
            if(ch[a[sx][sy]])
            {
                q[++sf]=mp(sx,sy);
                ch[g[sx][sy]]=1;
                viz[sx][sy]=1;
                actual(g[sx][sy]);
            }
            else
            {
                v[a[sx][sy]].push_back(mp(sx,sy));
                viz[sx][sy]=2;
            }
        }
        inc++;
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(viz[i][j]==1)
                sol+=viz[i][j];
    printf("%d\n",sol);
    return 0 ;
}