Cod sursa(job #1660709)

Utilizator CraiuAndrei Craiu Craiu Data 23 martie 2016 12:52:05
Problema Castel Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <bits/stdc++.h>

using namespace std;

ofstream fout("castel.out");

int n, m, k;
int u[40005], a[40005], c;

queue <int> q;
vector <int> lst[40005];

void Citire()
{
    int i, x, j;
    ifstream fin("castel.in");
    fin >> n >> m >> k;
    for(i = 1; i <= n; i++)
        for(j = 1; j <= m; j++)
        {
            fin >> x;
            ++c;
            lst[x].push_back(c);
            a[c] = x;
        }
    u[k] = 1;
}

void Eval(int y)
{
    if(u[y] == 0)
    {
        if(u[a[y]] == 1)
        {
            u[y] = 1;
            q.push(y);
        }
        else lst[a[y]].push_back(y);
    }
}

void Rezolva()
{
    int x, z, y;
    q.push(k);
    while(!q.empty())
    {
        x = q.front();
        q.pop();
        while(!lst[x].empty())
        {
            z = lst[x].back();
            u[z] = 1;
            q.push(z);
            lst[x].pop_back();
        }
        ///Nord
        y = x - m;
        if(y > 0)   Eval(y);
        ///Sud
        y = x + m;
        if(y <= n * m)   Eval(y);
        ///Est
        if(x % m != 0)
        {
            y = x + 1;
            Eval(y);
        }
        ///Vest
        if(x % m != 1)
        {
            y = x - 1;
            Eval(y);
        }
    }
    int sol = 0, i;
    for(i = 1; i <= n * m; i++)
        if(u[i] == 1) sol++;
    fout << sol << "\n";
    fout.close();
}

int main()
{
    Citire();
    Rezolva();
    return 0;
}