Cod sursa(job #2703327)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 8 februarie 2021 10:25:48
Problema Castel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("castel.in");
ofstream fout("castel.out");

int main() {
    int N, M, K;
    fin >> N >> M >> K;
    vector<vector<int>> a(N + 1, vector<int>(M + 1));
    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= M; ++j)
            fin >> a[i][j];
    vector<pair<int,int>> Hash(N * M + 1);
    Hash[1] = make_pair(1, 1);
    for(int i = 2; i <= N * M; ++i) {
        Hash[i] = Hash[i - 1];
        ++Hash[i].second;
        if(Hash[i].second == M + 1) {
            ++Hash[i].first;
            Hash[i].second = 1;
        }
    }
    queue<int> Q;
    Q.emplace(K);
    vector<bool> viz(N * M + 1);
    viz[K] = true;
    const int di[] = {-1, 0, 1, 0},
              dj[] = {0, 1, 0, -1};
    int ans = 0;
    vector<int> adj[N * M + 1];
    auto inside = [&](int lin, int col) -> bool {
        return lin > 0 && lin <= N && col > 0 && col <= M;
    };
    vector<int> av(N * M + 1);
    while(!Q.empty()) {
        int curr = Q.front();
        Q.pop();
        ++ans;
        av[curr] = true;
        for(const int &next : adj[curr])
            if(!viz[next]) {
                viz[next] = true;
                Q.emplace(next);
            }
        int i, j;
        tie(i, j) = Hash[curr];
        for(int k = 0; k < 4; ++k) {
            int iv = i + di[k],
                jv = j + dj[k];
            if(!inside(iv, jv) || viz[(iv - 1) * M + jv])
                continue;
            if(av[a[iv][jv]]) {
                Q.emplace((iv - 1) * M + jv);
                viz[(iv - 1) * M + jv] = true;
            }
            else
                adj[a[iv][jv]].emplace_back((iv - 1) * M + jv);
        }
    }
    fout << ans << '\n';
}