Cod sursa(job #2551080)

Utilizator ApostolIlieDanielApostol Daniel ApostolIlieDaniel Data 19 februarie 2020 14:18:35
Problema Castel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <bits/stdc++.h>

using namespace std;

int n, m, k;
#define pb push_back
int get_id (pair <int, int> x) {
    return x.second + (x.first - 1) * m;
}

pair <int, int> get_pair (int x) {
    return {(x - 1) / m + 1, (x - 1) % m + 1};
}
const int N = 150;
bool viz[1 + N][1 + N];
int key[1 + N][1 + N];
bool open[1 + N * N];
vector <int> rooms[1 + N * N];
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};

bool inside (pair <int, int> x) {
    return 1 <= x.first && x.first <= n && 1 <= x.second && x.second <= m;
}

int main () {
    freopen ("castel.in", "r", stdin);
    freopen ("castel.out", "w", stdout);

    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);

    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++)
            cin >> key[i][j];
    }

    queue <int> q;
    q.push (k);
    int ans = 0;
    auto c = get_pair (k);
    viz[c.first][c.second] = true;
    while (q.size ()) {
        int node = q.front ();
        q.pop (); ans++;
        auto c = get_pair (node);
        if (!open[node]) {
            open[node] = true;
            for (auto x : rooms[node])
                q.push (x);
        }
        for (int dir = 0; dir < 4; dir++) {
            pair <int, int> nc = {c.first + dx[dir], c.second + dy[dir]};
            if (inside (nc) && !viz[nc.first][nc.second]) {
                viz[nc.first][nc.second] = true;
                int val = key[nc.first][nc.second];
                if (open[val])
                    q.push (get_id (nc));
                else
                    rooms[val].pb (get_id (nc));
            }
        }
    }
    cout << ans << "\n";
    return 0;
}