Cod sursa(job #2638460)

Utilizator alex_braslasuBraslasu Alexandru alex_braslasu Data 28 iulie 2020 12:53:25
Problema Castel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.6 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], okk[40000];
vector<int > v[40000];
vector<int >::iterator it;
queue<int > q;

bool OK(int x, int poz)
{
    if (x < 1 || x > n * m)
        return false;
    if (!(x % m) && poz == 0)
        return false;
    if (x % m == 1 && poz == 1)
        return false;
    return true;
}

void Parcurge(int xs)
{
    int x, xx;
    ok[xs] = true;
    q.push(xs);
    while (!q.empty())
    {
        x = q.front();
        q.pop();
        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, i) && !ok[xx])
            {
                if (ok[a[xx]])
                {
                    ok[xx] = true;
                    ++nr;
                    q.push(xx);
                }
                else
                {
                    if (!okk[xx])
                    {
                        okk[xx] = true;
                        v[a[xx]].push_back(xx);
                    }
                }
            }
        }
    }
}

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;
}