Cod sursa(job #64075)

Utilizator blalaLaura Banias blala Data 1 iunie 2007 16:01:49
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.1 kb
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
using namespace std;

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

const int di[] = { 0, 1, 0, -1 };
const 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 + NMAX*NMAX > s, uz;

FILE *fout = fopen( out, "w" );
int rez;


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

 
void Read()
{
//    FILE *fin = fopen( in, "r" ); 
    freopen(in,"r",stdin);

    #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;   \
      }                                    \
    }
//    fscanf( fin, "%lh%lh%lh", &m, &n, &k );
    cit(m) cit(n) cit(k)
    int i, j;
    
    for ( i = 1; i <= m; ++i )
        for ( j = 1; j <= n; ++j )
                //fscanf( fin, "%lh", &ch[i][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] = true;
                uz[ch[i][j]] = true;
                s[ind] = true;
            }
            ind++;                   
        }
    } 
}

void Solve()
{
    rez = 1;
    int i, j, d, kap;
    bool ok = true;
    
    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]] = true;
                        uz[ch[iv][jv]] = true;
                        s[a[iv][jv]] = true;   
                        ok = true;
                        rez++;
                }    
            }
        }    
    } 

}    
 

#undef int
int main()
{   
    Read(); 
    Solve();
    
    fprintf( fout, "%d\n", (int)rez );    
    fclose( fout );
    return 0;
}