Cod sursa(job #2638192)

Utilizator alex_braslasuBraslasu Alexandru alex_braslasu Data 27 iulie 2020 14:37:48
Problema Castel Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <fstream>
#include <vector>
#include <iterator>
#include <queue>

using namespace std;

ifstream f("castel.in");
ofstream g("castel.out");

int n, m, k, i, nr = 1, j, a[40000];
int dx[] = {-1, 1, 0, 0};
bool ok[40000];
vector<int > v[40000];
vector<int >::iterator it;
queue<int > q;

bool OK(int x)
{
    if (x >= 1 && x <= n * m)
        return true;
    return false;
}

void Parcurge(int xs)
{
    int x, xx;
    ok[xs] = true;
    q.push(xs);
    while (!q.empty())
    {
        x = q.front();
        while (!v[x].empty())
        {
            if (!ok[v[x].back()])
                ++nr;
            ok[v[x].back()] = true;
            q.push(v[x].back());
            v[x].pop_back();
        }
        for (i = 0; i < 4; ++i)
        {
            xx = x + dx[i];
            if (!ok[xx] && OK(xx))
            {
                if (ok[a[xx]])
                {
                    ok[xx] = true;
                    ++nr;
                    q.push(xx);
                }
                else
                    v[a[xx]].push_back(xx);
            }
        }
        q.pop();
    }
}

int main()
{
    f >> n >> m >> k;
    for (i = 1; i <= n * m; ++i)
        f >> a[i];
    dx[2] += m;
    dx[3] -= m;
    Parcurge(k);
    g << nr;
    return 0;
}