Cod sursa(job #2684278)

Utilizator rares_ciocieaRares Andrei Ciociea rares_ciociea Data 13 decembrie 2020 14:22:07
Problema Castel Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <fstream>
#include <map>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

ifstream in("castel.in");
ofstream out("castel.out");
int matt[151][151];
int n, m;
int dx[] = { 0,0,0,1,-1 };
int dy[] = { 0,1,-1,0,0 };
struct nr {
    int x, y;
};
queue <nr>q, q1;
map <int, bool>mp;
bool ap[151][151];
bool apF[151][151];
bool inMat(int x, int y)
{
    if (x <= n && x >= 1 && y <= m && y >= 1)
        return 1;
    return 0;
}
pair <int, int> calc(int x)
{
    if (x % m == 0)
        return { x / m,m };
    return { x / m + 1,x % m };
}
void Fill(int x, int y)
{
    apF[x][y] = 1;
    ap[x][y] = 1;
    mp[(x-1)*m+y] =1;
    for (int i = 1; i <= 4; i++)
    {
        int x1 = x + dx[i], y1 = y + dy[i];
        if (ap[x1][y1])
            continue;
        if (inMat(x1, y1))
        {
            if (mp[matt[x1][y1]] == 0)
                q.push({ x1,y1 }),ap[x1][y1]=1;
            else Fill(x1, y1);
        }
    }
}
int main()
{
    int k;
    in >> n >> m >> k;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            in >> matt[i][j];
    pair <int, int>f = calc(k);
    mp[matt[f.first][f.second]] = 1;
    q.push({ f.first,f.second });
    while (!q.empty())
    {
        q1 = q;
        bool ok = 0;
        while (!q1.empty())
        {
            nr f = q1.front();
            if (mp[matt[f.x][f.y]] == 1)
                ok = 1;
            q1.pop();
        }
        if (ok == 0)
            break;
        nr plm = q.front();
        memset(ap, 0, sizeof ap);
        if (mp[matt[plm.x][plm.y]] == 1)
            Fill(q.front().x, q.front().y);
        else q.push(q.front());
        q.pop();
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (apF[i][j] == 1)
                cnt++;
    out << cnt;
    return 0;
}