Cod sursa(job #859296)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 20 ianuarie 2013 00:11:19
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream f ( "castel.in" );
ofstream g ( "castel.out" );
#define sh short int
#define LE 166
queue<pair<sh, sh> > que;
sh n, m,  i, j;
int k;
bool  fr[LE*LE];
sh  key[LE][LE], a[LE][LE];
bool viz[LE][LE];
vector <pair<sh, sh> > B[LE*LE];
int co;
void lee();
int color;
int result;
sh xx[] = {0, 0, 1, -1};
sh yy[] = {1, -1, 0, 0};
pair<sh, sh> X;

int main()
{
    f >> n >> m >> k;

    for ( i = 1; i <= n; ++i )
        for ( j = 1; j <= m; ++j )
        {
            f >> key[i][j];
            a[i][j] = ++co;

            if ( co == k )
                que.push ( make_pair ( i, j ) );
        }

    lee();

    g << result << '\n';

    f.close();
    g.close();
    return 0;
}

void lee()
{
    while ( que.empty() == false )
    {
        pair<sh, sh> t = que.front();
        que.pop();

        if ( viz[t.first][t.second] == false )
            ++result;
        else continue;

        viz[t.first][t.second] = true;

        color = a[t.first][t.second];

        for ( i = 0; i < 4; ++i )
        {
            X = make_pair ( t.first + xx[i], t.second + yy[i] );

            if ( viz[X.first][X.second] == false && a[X.first][X.second] )
            {
                if ( fr[key[X.first][X.second]] == true )
                    que.push ( X );
                else  B[key[X.first][X.second]].push_back ( X );
            }
        }

        if ( fr[color] == false )
        {
            sh N = B[color].size();

            for ( i = 0; i < N; ++i )
                que.push ( B[color][i] );

            B[color].clear();
            fr[color] = true;
        }
    }
}