Cod sursa(job #63846)

Utilizator TabaraTabara Mihai Tabara Data 31 mai 2007 09:45:57
Problema Castel Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.52 kb
#include <fstream>
using namespace std;

#define in "castel.in"
#define out "castel.out"
#define NMAX 51

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

struct Num {
    int i;
    int j;
} q[NMAX*NMAX];

int a[NMAX][NMAX];
int ch[NMAX][NMAX];
int n, m, k, prim, ultim, iv, jv;
int s[NMAX*NMAX], uz[NMAX*NMAX];

void Read();
void Solve();

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

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

int main()
{
    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 ) 
            {
                ultim++;//1
                prim++;//1
                q[ultim].i = i;
                q[ultim].j = j;
                uz[ind] = 1;
                uz[ch[i][j]] = 1;
                s[ind] = 1;
            }
            ind++;                   
        }
    } 
    /*for ( i = 1; i <= m; ++i )
    {
        for ( j = 1; j <= n; ++j )
        {
            fprintf( fout, "%d ", a[i][j] );
        }
        fprintf( fout, "\n" );
    }        
          
    fprintf( fout, "%d %d\n", q[prim].i, q[prim].j );*/
    fclose( fin );
}

void Solve()
{
    rez = 1;
    int i, j, d;
    bool ok = true;
    
    while ( ok )
    {
        ok = false;
        for ( prim = 1; prim <= ultim; ++prim )
        {            
            i = q[prim].i;
            j = q[prim].j;
            for ( d = 0; d < 4; ++d )
            {
                iv = i + di[d];
                jv = j + dj[d];
                if ( Ok(iv,jv) )
                {
                        ultim++;
                        q[ultim].i = iv;
                        q[ultim].j = jv;
                        uz[a[iv][jv]] = 1;
                        uz[ch[iv][jv]] = 1;
                        s[a[iv][jv]] = 1;   
                        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]] == 1 ) return 0;
    if ( !uz[ch[i][j]] ) return 0;
    return 1;
}