Cod sursa(job #2958319)

Utilizator AswVwsACamburu Luca AswVwsA Data 25 decembrie 2022 22:45:12
Problema Castel Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.05 kb
//Sepultura rupe
#include <fstream>
#include <algorithm>
#include <climits>
#include <queue>
#define ll long long
using namespace std;

const int NMAX = 150;

int di[] = {-1, 1, 0, 0};
int dj[] = {0, 0, -1, 1};

int v[NMAX + 1][NMAX + 1];

bool seen[NMAX + 1][NMAX + 1], in[NMAX + 1][NMAX + 1];

int n, m;

int cnt, pas;
bool ok;

queue <pair <int, int> > q;

bool viz[NMAX * NMAX + 1];

bool inside(int a, int b)
{
    return a >= 1 and a <= n and b >= 1 and b <= m;
}

struct idfk
{
    int i, j;
    int time;
};

queue <idfk> restant;

void verifica(int ni, int nj)
{
    if (!seen[ni][nj] and inside(ni, nj))
    {
        if (viz[v[ni][nj]])
        {
            cnt++;
            seen[ni][nj] = 1;
            int key = (ni - 1) * m + nj;
            viz[key] = 1;
            q.push({ni, nj});
        }
        else if (!in[ni][nj])
        {
            in[ni][nj] = 1;
            ok = 1;
            restant.push({ni, nj, pas});
        }
    }
}
int main()
{
    ifstream cin("castel.in");
    ofstream cout("castel.out");
    int k, i, j;
    cin >> n >> m >> k;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
        {
            cin >> v[i][j];
        }
    int col = k % m;
    if (col == 0)
        col = m;
    q.push({k / m + bool(k % m), col});
    cnt = 1;
    viz[k] = 1;
    seen[k / m + bool(k % m)][col] = 1;
    pas = 0;
    ok = 0;
    do
    {
        ok = 0;
        while (!q.empty())
        {
            pair <int, int> f = q.front();
            q.pop();
            bool nou = 0;
            for (i = 0; i < 4; i++)
            {
                int nj = f.second + dj[i];
                int ni = f.first + di[i];
                verifica(ni, nj);
            }
        }
        pas++;
        while (!restant.empty())
        {
            idfk f = restant.front();
            if (f.time == pas)
                break;
            restant.pop();
            verifica(f.i, f.j);
        }
    }
    while (ok);
    cout << cnt;
}