Cod sursa(job #158921)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 13 martie 2008 21:22:50
Problema Castel Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <stdio.h>
#include <vector>
#include <bitset>

using namespace std;

long n,m,i,j,k,p,q,li,ci;
long x[22505],y[22205],a[151][151];
long xx,yy,pa,pb,ok;
long dx[]={-1,0,1,0};
long dy[]={0,1,0,-1};
bitset <160>mark[160];
bitset <22505>key;
vector <int>v[22505];

void vizitare(int x){
     long i,l;
     l=v[x].size();
     if (l){
        for (i=0;i<v[x].size();i++){
            xx=v[x][i]/m;
            yy=v[x][i]%m;
            if (yy==0)yy=m;
            else xx++;
            mark[xx][yy]=1;
            key[v[x][i]]=1;
            ok=1;
            for (k=0;k<4;k++){
                pa=xx+dx[k];
                pb=yy+dy[k];
                if (pa>0&&pa<=n)
                   if (pb>0&&pb<=m)
                      if (!mark[pa][pb])
                         v[a[pa][pb]].push_back((pa-1)*m+pb);
            }
        }
        v[x].clear();
     }
}                

int main(){
    freopen("castel.in","r",stdin);
    freopen("castel.out","w",stdout);
    
    scanf("%ld %ld %ld",&n,&m,&k);
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            scanf("%ld",&a[i][j]);
    key[k]=1;
    li=k/m;
    if (k%m==0)ci=m;
    else {li++;ci=k%m;}
    
    p=1;q=1;
    x[1]=li;y[1]=ci;
    mark[li][ci]=1;
    while (p<=q){
          for (k=0;k<4;k++){
              xx=x[p]+dx[k];
              yy=y[p]+dy[k];
              if (xx>0&&xx<=n)
                 if (yy>0&&yy<=m)
                    if (!mark[xx][yy])
                       if (key[a[xx][yy]]){
                          q++;
                          x[q]=xx;y[q]=yy;
                          mark[xx][yy]=1;
                          key[(xx-1)*m+yy]=1;
                       }
                       else v[a[xx][yy]].push_back((xx-1)*m+yy);
          }
          p++;
    }
    ok=1;
    while (ok){
          ok=0;
          for (i=1;i<=n*m;i++)
              if (key[i])
                 vizitare(i);
    }
    p=0;
    for (i=1;i<=n;i++){
        for (j=1;j<=m;j++)
            if(mark[i][j]){p++;/*printf("1 ");*/}
            //else printf ("0 ");
        //printf("\n");
    }
    printf("%ld\n",p);
    
return 0;
}