Cod sursa(job #859280)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 19 ianuarie 2013 23:47:55
Problema Castel Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream f ( "castel.in" );
ofstream g ( "castel.out" );
#define LE 166
queue<pair<int, int> > que;
int n, m, k, i, j;
bool  fr[LE*LE];
int key[LE][LE], a[LE][LE];
bool viz[LE][LE];
vector <pair<int, int> > B[LE*LE];
int co;
void lee();
int color;
int result;
int xx[] = {0, 0, 1, -1};
int yy[] = {1, -1, 0, 0};
pair<int, int> 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<int, int> t = que.front();
        que.pop();

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

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

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

        for ( i = 0; i < 3; ++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 )
        {
            int N = B[color].size();

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

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