Cod sursa(job #1238757)

Utilizator borcanirobertBorcani Robert borcanirobert Data 7 octombrie 2014 17:46:21
Problema Castel Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <cstdio>
#include <queue>
using namespace std;

const int MAX = 155;
const int di[] = { 0, 1, 0, -1 };
const int dj[] = { 1, 0, -1, 0 };
queue <int> Q;
int a[MAX][MAX];
bool fa[MAX][MAX];
bool c[MAX * MAX];
bool op[MAX * MAX];
int N, M, K;
int nr;
int x, y;

int ri( int a ) { if ( a % M == 0 ) return ( a / M ); else return ( a / M ) + 1; }
int rj( int a ) { return a - ( ri(a) - 1 ) * M; }
void Lee();
bool Search();
bool OK( int i, int j );

int main()
{
    freopen("castel.in", "r", stdin);
    freopen("castel.out", "w", stdout);

    int i, j;

    scanf( "%d%d%d", &N, &M, &K );
    for ( i = 1; i <= N; i++ )
        for ( j = 1; j <= M; j++ )
            scanf( "%d", &a[i][j] );

    Lee();

    printf( "%d\n", nr );

    fclose(stdin);
    fclose(stdout);
    return 0;
}

void Lee()
{
    int i, j, d, d1, p, q;
    Q.push( K ); c[K] = 1;

    while ( !Q.empty() && Search() )
    {
        nr++;
        c[( ( x - 1 ) * M ) + y] = 1;
        fa[x][y] = 1;

        for ( d = 0; d < 4; d++ )
        {
            i = di[d] + x;
            j = dj[d] + y;

            if ( OK( i, j ) )
            {
                if ( fa[i][j] )
                    continue;
                Q.push( ( ( i - 1 ) * M ) + j );
            }
        }
    }
}

bool Search()
{
    int v[MAX * MAX], nv, i;
    nv = 0;
    bool ok;
    ok = false;

    if ( x == 2 && y == 1 )
        ok = false;

    while ( !Q.empty() && !ok )
    {
        v[++nv] = Q.front();
        Q.pop();

        if ( c[a[ri(v[nv])][rj(v[nv])]] && !fa[ri(v[nv])][rj(v[nv])] )
            ok = true;
    }

    if ( !ok )
        return false;
    for ( i = 1; i < nv; i++ )
        Q.push(v[i]);
    x = ri(v[nv]);
    y = rj(v[nv]);
    return true;
}

bool OK( int i, int j )
{
    if ( i <= N && j <= M && i > 0 && j > 0 )
        return true;
    return false;
}