Cod sursa(job #2738188)

Utilizator vansJos da pa perete vans Data 5 aprilie 2021 15:45:26
Problema Castel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 150;

const int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
int n, m, k, v[NMAX + 1][NMAX + 1], ans;
bool w[NMAX * NMAX + 1];
bitset<NMAX * NMAX + 1> unlocked;

inline int a(const int X, const int Y) {
    return (X - 1) * m + Y;
}

inline pair<int, int> opa(const int X) {
    return {(X - 1) / m + 1, (X - 1) % m + 1};
}

inline bool inBounds(const int X, const int Y) {
    return min(X, Y) >= 1 && X <= n && Y <= m;
}

void bfs_sau_cum_ii_zice() {
    int SX, SY;
    tie(SX, SY) = opa(k),
    w[k] = 1;

    queue<int> q;
    q.push(k);

    vector<int> recov[NMAX * NMAX + 1];

    while(!q.empty()) {
        const int crt = q.front();
        int cx, cy;
        tie(cx, cy) = opa(crt);
        q.pop();

        unlocked[crt] = 1, ++ans;

        for(const auto &el : recov[crt])
            if(!w[el]) w[el] = 1, q.push(el);

        for(int i = 0; i < 4; ++i) {
            const int ncx = cx + dx[i], ncy = cy + dy[i], ncrt = a(ncx, ncy);
            if(inBounds(ncx, ncy) && !w[ncrt]) {
                if(unlocked[v[ncx][ncy]]) w[ncrt] = 1, q.push(ncrt);
                else recov[v[ncx][ncy]].push_back(ncrt);
            }
        }
    }
}

int main()
{
    freopen("castel.in", "r", stdin);
    freopen("castel.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j) scanf("%d", &v[i][j]);
    bfs_sau_cum_ii_zice();
    printf("%d", ans);
    return 0;
}