Cod sursa(job #64069)

Utilizator TabaraTabara Mihai Tabara Data 1 iunie 2007 15:36:25
Problema Castel Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.34 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
//70 puncte
#define in "castel.in"
#define out "castel.out"
#define NMAX 151

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

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

short int a[NMAX][NMAX];
short int ch[NMAX][NMAX];
int n, m, k, iv, jv;
vector<bool> s, uz;

void Read();
void Solve();

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

int Ok(int i, int j);
int rez;

int main()
{
    uz.resize( NMAX*NMAX + NMAX*NMAX );
    s.resize( NMAX*NMAX + NMAX*NMAX );
    
    Read(); 
    Solve();
    
    fprintf( fout, "%d\n", rez );    
    fclose( fout );
    return 0;
}    
 
void Read()
{
    FILE *fin = fopen( in, "r" ); 
    fscanf( fin, "%d%d%d", &m, &n, &k );
    int i, j;
    
    for ( i = 1; i <= m; ++i )
        for ( j = 1; j <= n; ++j )
                fscanf( fin, "%d", &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++;                   
        }
    } 
    fclose( fin );
}

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++;
                }    
            }
        }    
    } 

}    

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;
}