Cod sursa(job #2958381)

Utilizator AswVwsACamburu Luca AswVwsA Data 26 decembrie 2022 12:53:26
Problema Castel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.95 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];
int 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;
}

vector <pair <int, int> > idee[NMAX * NMAX + 1]; //idee blanao cu ceva structuri
//care tin minte ce intra din vecini si se deschide cu cheia indice

vector <int> keys;
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;
    bool ok;
    do
    {
        ok = 0;
        while (!q.empty())
        {
            pair <int, int> f = q.front();
            q.pop();
            if (!seen[f.first][f.second])
            {
                seen[f.first][f.second] = 1;
                cnt++;
                int key = (f.first - 1) * m + f.second;
                if (!viz[key])
                {
                    keys.push_back(key);
                    ok = 1;
                }
                viz[key] = 1;
            }
            for (i = 0; i < 4; i++)
            {
                int ni = f.first + di[i];
                int nj = f.second + dj[i];
                if (inside(ni, nj) and !seen[ni][nj])
                {
                    if (viz[v[ni][nj]])
                    {
                        cnt++;
                        seen[ni][nj] = 1;
                        int key = (ni - 1) * m + nj;
                        if (!viz[key])
                        {
                            keys.push_back(key);
                            ok = 1;
                        }
                        viz[key] = 1;
                        q.push({ni, nj});
                    }
                    else if (!in[ni][nj])
                    {
                        idee[v[ni][nj]].push_back({ni, nj});
                        in[ni][nj] = 1;
                    }
                }
            }
        }
        while (!keys.empty())
        {
            int val = keys.back();
            keys.pop_back();
            while (!idee[val].empty())
            {
                q.push({idee[val].back().first, idee[val].back().second});
                idee[val].pop_back();
            }
        }
    }
    while (ok);

    /*for (i = 1; i <= n; i++, cout << "\n")
        for (j = 1; j <= m; j++)
            cout << seen[i][j] << " ";*/
    cout << cnt;
}