Cod sursa(job #859249)

Utilizator cat_red20Vasile Ioana cat_red20 Data 19 ianuarie 2013 22:34:22
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include<stdio.h>
#include<vector>
int a[151][151],m,n,q[22501],p,u,k,rez;
bool viz[151][151];
const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
std::vector < int > l[22501];

void citire()
{
    freopen("castel.in","r",stdin);
    scanf("%d %d %d",&m,&n,&k);
    k--;
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            scanf("%d",&a[i][j]);
            a[i][j]--;
        }
    }
    for(int i=0;i<=m;i++)
    a[i][n]=-1;
    for(int j=0;j<=n;j++)
    a[m][j]=-1;
}

void adaugare(int x,int y)
{
    int t=x*n+y,k;
    while(!l[t].empty())
    {
        k=l[t].back();
        q[++u]=k;
        l[t].pop_back();
        adaugare(k/n,k%n);
        viz[k/n][k%n]=1;
    }
}

void lee()
{
    int x,y;
    p=u=1;
    q[1]=k;
    viz[k/n][k%n]=1;
    while(p<=u)
    {
        for(int i=0;i<=3;i++)
        {
            x=q[p]/n+dx[i];
            y=q[p]%n+dy[i];
            if(x<0 || x>=m || y<0 || y>=n)
            continue;
            if (viz[x][y]==1)
            continue;
            if(viz[a[x][y]/n][a[x][y]%n]==1)
            {
                u++;
                q[u]=x*n+y;
                viz[x][y]=1;
                adaugare(x,y);
            }
            else
            {
                l[a[x][y]].push_back(x*n+y);
            }
        }
        p++;
    }
}

void afisare()
{
    freopen("castel.out","w",stdout);
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        rez+=viz[i][j];
    }
    printf("%d",rez);
}

int main()
{
    citire();
    lee();
    afisare();
    return 0;
}