Cod sursa(job #64204)

Utilizator crawlerPuni Andrei Paul crawler Data 1 iunie 2007 23:49:58
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.77 kb
#include <cstdio>
#include <vector>
#include <bitset>

using namespace std;

#define in "castel.in"
#define out "castel.out"
#define Nmax 151
#define int short

int di[] = { 0, 1, 0, -1 };
int dj[] = { 1, 0, -1, 0 };

vector<int> qi;
vector<int> qj;

int a[Nmax][Nmax];
int ch[Nmax][Nmax];
int n, m, k, iv, jv;
bitset< Nmax*Nmax*2 > s, uz;

int ret;

int Ok(int i, int j)
{
    if ( i < 1 || i > m || j < 1 || j > n ) return 0;
    if ( s[a[i][j]] == 1 ) return 0;
    if ( uz[ch[i][j]] == 0 ) return 0;
    return 1;
}

#undef int
int main()
{   
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);

    #define dim 10000
    int poz = 0;char buf[dim];
    fread(buf,1,dim,stdin);
    #define cit(x)                         \
    {                                      \
     x = 0;                                \
     while(buf[poz] < '0')                 \
      {                                    \
       ++poz;                              \
       if(poz == dim)                      \
         fread(buf,1,dim,stdin), poz = 0;  \
      }                                    \
     while(buf[poz] >= '0')                \
      {                                    \
       x = x*10 + buf[poz] - '0';          \
       if(++poz == dim)                    \
        fread(buf,1,dim,stdin), poz = 0;   \
      }                                    \
    }
    cit(m) cit(n) cit(k)
    int i,j;
    
    for ( i = 1; i <= m; ++i )
        for ( j = 1; j <= n; ++j )
               cit(ch[i][j]); 
                
    int ind = 1;
    for ( i = 1; i <= m; ++i )
    {
        for ( j = 1; j <= n; ++j )
        {
            a[i][j] = ind;
            if ( ind == k ) 
            {                               
                qi.push_back(i);
                qj.push_back(j);
                uz[ind] = 1;
                uz[ch[i][j]] = 1;
                s[ind] = 1;
            }
            ind++;                   
        }
    } 

    ret = 1;
    int d, kap;
    bool ok = 1;
    
    while ( ok )
    {
        ok = false;
        for ( kap = 0; kap < qi.size(); ++kap )
        {            
            i = qi[kap];
            j = qj[kap];
            for ( d = 0; d < 4; ++d )
            {
                iv = i + di[d];
                jv = j + dj[d];
                if ( Ok(iv,jv) )
                {
                        qi.push_back(iv);
                        qj.push_back(jv);
                        uz[a[iv][jv]] = 1;
                        uz[ch[iv][jv]] = 1;
                        s[a[iv][jv]] = 1;
                        ok = 1;
                        ret++;
                }    
            }
        }    
    } 
    
    printf("%d\n",(int)ret);
    return 0;
}